题意:4维空间中有1个点集A，|A|=n,用(a,b,c,d)表示每个点。共有m个询问，每次询问输入一个点(a,b,c,d)，求最大的S,其中S={p|p∈A且ap<=a,bp<=b,cp<=c,dp<=d}，输出|S|输入格式：第一行n接下来n行有n个4维点对第n+2行有一个数m再接下来m行每行有一个四维点对，表示每个询问输出格式：对于每个询问输出一个数**方法:**bitset优化 或 排序+cdq分治+树状数组+平衡树解析:神题，考场不会，暴力骗40，据说bz陌上花开跟这道题类似?差一维呢！基本思想是降维不过怎么做呢？考场我也就想了个排序降1维之后弃疗后来才懂怎么降，太神了首先第一维排序，然后对第二维cdq分治。第一维不用说，精度也不卡，随便排一下就好了，之后cdq分治步骤：划分->递归左区间->右区间询问处理->搞右区间->归并妈妈我之前学个鬼cdq了之后有个需要注意的，就是排序第一维的时候，第二关键字是是否是询问。cdq前sort下第二维，或者你在里面搞也行无所谓了。不过外面搞快，这是必然的。然后呢，上一个树状数组。每个树状数组节点再开个平衡树。好像是我刚写了个线段树套线段树所以这部分好写咯？注意:第三维需要离散，不然开不了树状数组。每次搞完一次cdq的时候，需要d掉原来的树套树，由于动态开点？所以我们只需要size赋零，清一遍树状数组的root。当然实测memset root 是可以过的，不过这么做太暴力了，我们可以把树状数组的过程重新演算一遍，把赋过的root搞成0就好了。之后这道题就OK了？不好写是不好写！不过蒟蒻我还是艰难地写出来了，最后那个AC真的是真心的爽！不过呢？让我们来想一个问题，如果题中的4维变成了5维怎么写？卧槽树套树套树？我选择死亡
所以专门有神奇的优化方式来处理这种问题？先想一个暴力对于每一维，单独排序，对于每个询问，肯定都是每一维开始的连续一段能单独满足这一维，所以呢，我们要是找这四维中最短的一段，，枚举所有段内的元素，将所有可行的元素添加到答案里。这很暴力，也很赌数据
不过有bitset啊每一次排序所有元素，排序所有询问，之后像cdq中那么处理，添加一段更新一次添加一段更新一次。讨论第一维的时候直接赋上该询问的bitset，后三维的话就是&原来的bitset就OK了。好像比正解慢了0.2s。代码:bitsetusing namespace std;int n,m;struct node{double a[5];int no;}a[N],b[N];bitset<N>bit[N],bit2;.a[1]<y.a[1];}.a[2]<y.a[2];}.a[3]<y.a[3];}.a[4]<y.a[4];} int main(){scanf(“%d”,&n);”,&a[i].a[1],&a[i].a[2],&a[i].a[3],&a[i].a[4]),a[i].no=i;scanf(“%d”,&m);”,&b[i].a[1],&b[i].a[2],&b[i].a[3],&b[i].a[4]),b[i].no=i;for(int i=1;i<=4;i++){switch(i){case 1:sort(a+1,a+n+1,cmp1);sort(b+1,b+m+1,cmp1);break;case 2:sort(a+1,a+n+1,cmp2);sort(b+1,b+m+1,cmp2);break;case 3:sort(a+1,a+n+1,cmp3);sort(b+1,b+m+1,cmp3);break;case 4:sort(a+1,a+n+1,cmp4);sort(b+1,b+m+1,cmp4);break;}int l1=1,l2=1;while(l2<=m){while(a[l1].a[i]<=b[l2].a[i]&&l1<=n){bit2[a[l1].no]=1;l1++;}if(i==1)bit[b[l2].no]=bit2;else bit[b[l2].no]&=bit2;l2++;}bit2=0;}for(int i=1;i<=m;i++)printf(“%d\n”,bit[i].count());}正解！！using namespace std;int n,m,size,tot;&(-x);}struct treap{double v;int w;int l,r,size,rnd;}tr[N*30];struct node{double a,b,c,d;int newc;int no;int opt;}a[N<<1],b[N<<1],nq[N<<1];int ans[N];int root[N<<1];double gainc[N<<1];int cmp(node x,node y){if(x.a==y.a)return x.opt<y.opt;return x.a<y.a;}int cmp2(node x,node y){if(x.b==y.b)return x.opt<y.opt;return x.b<y.b;}void pushup(int rt){tr[rt].size=tr[tr[rt].l].size+tr[tr[rt].r].size+tr[rt].w;}void lturn(int &rt){int t=tr[rt].r;tr[rt].r=tr[t].l;tr[t].l=rt;tr[t].size=tr[rt].size;pushup(rt);rt=t;}void rturn(int &rt){int t=tr[rt].l;tr[rt].l=tr[t].r;tr[t].r=rt;tr[t].size=tr[rt].size;pushup(rt);rt=t;}void ins(int &rt,double v){if(!rt){rt=++size;tr[rt].size=1,tr[rt].l=0,tr[rt].r=0;tr[rt].w=1,tr[rt].v=v,tr[rt].rnd=rand();return;}tr[rt].size++;if(v==tr[rt].v)tr[rt].w++;else if(v<tr[rt].v){ins(tr[rt].l,v);if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt);}else{ins(tr[rt].r,v);if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt);}}int getrnk(int rt,double v){if(!rt)return 0;if(v<tr[rt].v){return getrnk(tr[rt].l,v);}else{int tmp=tr[tr[rt].l].size+tr[rt].w;return tmp+getrnk(tr[rt].r,v);}}void clr(int x){while(x<=tot&&root[x]){root[x]=0;x+=lowbit(x);}}void update(int x,double num){while(x<=tot){ins(root[x],num);x+=lowbit(x);}}int getans(int x,double num){int ret=0;while(x){ret+=getrnk(root[x],num);x-=lowbit(x);}return ret;}void cdq(int l,int r){int mid=(l+r)>>1;if(l>=r){return;}int l1=l,l2=mid+1;for(int i=l;i<=r;i++){if(a[i].no<=mid)nq[l1++]=a[i];else nq[l2++]=a[i];}for(int i=l;i<=r;i++)a[i]=nq[i];cdq(l,mid);l1=l;for(int i=mid+1;i<=r;i++){if(a[i].opt==0)continue;while(l1<=mid&&a[l1].b<=a[i].b){if(a[l1].opt==0){update(a[l1].newc,a[l1].d);}l1++;}ans[a[i].opt]+=getans(a[i].newc,a[i].d);}size=0;while(l1>=l){if(a[l1].opt==0){clr(a[l1].newc);}l1–;}cdq(mid+1,r);l1=l,l2=mid+1;for(int i=l;i<=r;i++){if((a[l1].b<a[l2].b||(a[l1].b==a[l2].b&&a[l1].no<a[l2].no)||l2>r)&&l1<=mid)nq[i]=a[l1++];else nq[i]=a[l2++];}for(int i=l;i<=r;i++)a[i]=nq[i];}int main(){scanf(“%d”,&n);”,&a[i].a,&a[i].b,&a[i].c,&a[i].d);scanf(“%d”,&m);”,&a[i+n].a,&a[i+n].b,&a[i+n].c,&a[i+n].d),a[i+n].opt=i;for(int i=1;i<=n+m;i++){gainc[i]=a[i].c;}sort(gainc+1,gainc+n+m+1);tot=unique(gainc+1,gainc+n+m+1)-gainc-1;for(int i=1;i<=n+m;i++)a[i].newc=lower_bound(gainc+1,gainc+tot+1,a[i].c)-gainc;sort(a+1,a+n+m+1,cmp);for(int i=1;i<=n+m;i++)a[i].no=i;sort(a+1,a+n+m+1,cmp2);cdq(1,n+m);for(int i=1;i<=m;i++){printf(“%d\n”,ans[i]);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
