矩形藏宝地

这题虽然题面有种自相矛盾的感觉，但是样例还是清晰的，简单题
题意：在一个二维平面上，求有多少个矩形是被包含在一个更大的矩形中的。

思路：伪四维偏序

  1. 由于题目竟然没有给出坐标的范围，因此我们拿到坐标还是离散化一下吧
  2. 现将所有的矩形按照 x 2 x2 x2（先按 y 2 y2 y2也行）从大到小排序，然后直接分治（至于为什么从大到小，想一下就好了）
  3. 在分治中为了保证第一维( x 2 x2 x2)的有序性，要先处理左右两个区间，再考虑左区间对右区间的影响
  4. 然后将左右区间按照 y 2 y2 y2从大到小排序，正常地运用双指针
  5. 对于左区间要插入树状数组的点，在树状数组的 x 1 x1 x1位置插入 y 1 y1 y1（反过来也行）
  6. 此处树状数组维护的是前缀最小值，我们对于每个右区间的点，在树状数组上查询 x 1 x1 x1，若返回的结果小于 y 1 y1 y1，则说明有一个更大的矩形将此矩形包含其中，打上“被包含”的标记即可
  7. 思考这样随便处理一下为什么就可以说明左区间有一个矩形包含了当前矩形呢？首先，我们是按照 x 2 x2 x2从大到小排序的，左区间所有点的 x 2 x2 x2都大于右区间的 x 2 x2 x2；然后我们又按照 y 2 y2 y2从大到小的进行插入和枚举，所以后遍历到的点的 y 2 y2 y2也是小于先遍历到的点的 y 2 y2 y2；而且我们是按照 x 1 x1 x1进行插入和询问的，所询问前缀位置显然是小于所询问的 x 1 x1 x1的，而且插入的值还是 y 1 y1 y1，因此比较询问到的 y 1 y1 y1和当前枚举的 y 1 y1 y1即可完成最后一维的比较。
  8. 至此，四个维度的前三个维度都是按照顺序的，第四个维度一比较，就知道当前矩形是否被另外一个矩形包含了。
  9. 那么，为什么要将其叫做伪四维偏序呢？因为对于第四个维度，我们只需要知道是否有满足这样大小关系的点，而不需要统计这样的点的数量，这样难度会大大减小。我们可以设想陌上开花如果改成四维的统计，那才是真正的要强行再套上一个数据结构！而不是想这道题可以巧妙的求解。

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e5+10;
const int mod = 2e9+7;
const double eps = 1e-9;

struct P{
    int x1, y1, x2, y2, f;
    P() {}
    P(int x1, int y1, int x2, int y2, int f): x1(x1), y1(y1), x2(x2), y2(y2), f(f) {}
}p[maxn];

bool cmp1(const P &a, const P &b) {
    return a.x2>b.x2;
}

bool cmp2(const P &a, const P & b) {
    return a.y2>b.y2;
}

int N;
int b[maxn*2], xx[maxn*2], yy[maxn*2];

inline void min(int &x, int y) { if(x>y) x=y; }
inline void clear(int x) { while(x<=N*2) b[x]=1e8, x+=x&-x; }
inline void update(int x, int d) { while(x<=N*2) min(b[x],d), x+=x&-x; }
inline int query(int x) { int ans=1e8; while(x) min(ans,b[x]), x-=x&-x; return ans; }

void solve(int l, int r) {
    if(l==r) return;
    int m=(l+r)/2;
    solve(l,m), solve(m+1,r);
    sort(p+l,p+m+1,cmp2), sort(p+m+1,p+r+1,cmp2);
    int j=l;
    for(int i=m+1; i<=r; ++i) {
        if(p[i].f) continue;
        while(j<=m&&p[j].y2>p[i].y2) update(p[j].x1,p[j].y1), ++j;
        int tmp=query(p[i].x1);
        if(tmp<p[i].y1) p[i].f=1;
    }
    while(--j>=l) clear(p[j].x1);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    N=read();
    for(int i=1; i<=2*N; ++i) b[i]=1e8;
    int cntx=0, cnty=0;
    for(int i=1; i<=N; ++i) {
        int x1=read(), y1=read(), x2=read(), y2=read();
        xx[++cntx]=x1, xx[++cntx]=x2;
        yy[++cnty]=y1, yy[++cnty]=y2;
        p[i]=P(x1,y1,x2,y2,0);
    }
    sort(xx+1,xx+1+cntx); sort(yy+1,yy+1+cnty);
    for(int i=1; i<=N; ++i) {
        p[i].x1=lower_bound(xx+1,xx+1+cntx,p[i].x1)-xx;
        p[i].x2=lower_bound(xx+1,xx+1+cntx,p[i].x2)-xx;
        p[i].y1=lower_bound(yy+1,yy+1+cnty,p[i].y1)-yy;
        p[i].y2=lower_bound(yy+1,yy+1+cnty,p[i].y2)-yy;
    }
    sort(p+1,p+1+N,cmp1);
    solve(1,N);
    int cnt=0;
    for(int i=1; i<=N; ++i) if(p[i].f) cnt++;
    printf("%d\n", cnt);
}