[BZOJ1790][AHOI2008]Rectangle 矩形藏宝地(四维偏序,CDQ+线段树)

题意显然的四维偏序，但是有不同的地方，这里求的不是满足条件的对数，而是只有0和1的判断，所以可以用三维偏序做。

按照常规方法，对a分治，对b排序，这时候我们询问的其实就是“到当前为止的所有c'>=c的矩形中，最大的d'是否大于d”，这个就是线段树后缀最大值。

 #include<cstdio>

 #include<algorithm>

 #define ls (x<<1)

 #define rs (ls|1)

 #define lson ls,L,mid

 #define rson rs,mid+1,R

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 using namespace std;

 const int N=;

 int n,ans,tot,b[N],res[N],tag[N],v[N<<],mx[N<<];

 struct P{ int a,b,c,d,id; }a[N],p[N];

 bool operator <(const P &a,const P &b){ return a.a<b.a; }

 bool cmp(const P &a,const P &b){ return a.b<b.b; }

 void upd(int x,int L,int R,int pos,int k){

     if (L==R){ v[x]=mx[x]=k; return; }

     int mid=(L+R)>>;

     if (pos<=mid) upd(lson,pos,k); else upd(rson,pos,k);

     mx[x]=max(mx[ls],mx[rs]);

 }

 int que(int x,int L,int R,int pos){

     if (L==R) return mx[x];

     int mid=(L+R)>>;

     if (pos<=mid) return max(que(lson,pos),mx[rs]);

         else return que(rson,pos);

 }

 void CDQ(int l,int r){

     if (l==r) return;

     int mid=(l+r)>>;

     CDQ(l,mid); CDQ(mid+,r);

     rep(i,l,mid) tag[a[i].id]=;

     rep(i,l,r) p[i]=a[i];

     sort(p+l,p+r+,cmp);

     rep(i,l,r){

         if (tag[p[i].id]) upd(,,n,p[i].c,p[i].d);

         else if (que(,,n,p[i].c)>p[i].d) res[p[i].id]=;

     }

     rep(i,l,mid) upd(,,n,a[i].c,),tag[a[i].id]=;

 }

 int main(){

     freopen("bzoj1790.in","r",stdin);

     freopen("bzoj1790.out","w",stdout);

     scanf("%d",&n);

     rep(i,,n) scanf("%d%d%d%d",&a[i].a,&a[i].b,&a[i].c,&a[i].d),b[i]=a[i].c,a[i].id=i;

     sort(b+,b+n+); tot=unique(b+,b+n+)-b-;

     rep(i,,n) a[i].c=lower_bound(b+,b+tot+,a[i].c)-b;

     sort(a+,a+n+); CDQ(,n);

     rep(i,,n) ans+=res[i]; printf("%d\n",ans);

     return ;

 }