cdq
三维偏序
#include<bits/stdc++.h> using namespace std; const int maxn= 2e5+5; struct node{int x,y,z,w,ct;}a[maxn],b[maxn]; int ans[maxn],BIT[maxn],B; bool cmp(node a,node b){ if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; return a.z<b.z; } bool equal(node a,node b){ return a.x==b.x&&a.y==b.y&&a.z==b.z; } void add(int i,int d){ for(;i<=B;i+=i&-i) BIT[i]+=d; } int sum(int i){ int ret=0; for(;i>=1;i-=i&-i) ret+=BIT[i]; return ret; } void cdq(int l,int r){ if(l==r) return; int mid=l+r>>1; cdq(l,mid), cdq(mid+1,r); int u=l,v=mid+1; for(int i=l;i<=r;i++) { if(v>r||(u<=mid&&a[u].y<=a[v].y)){ b[i]=a[u++]; add(b[i].z,b[i].ct); } else{ b[i]=a[v++]; b[i].w+=sum(b[i].z); } } for(int i=l;i<=mid;i++) add(a[i].z,-a[i].ct); for(int i=l;i<=r;i++) a[i]=b[i]; } int main(){ int n,k; scanf("%d%d",&n,&k); B=k; for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+1+n,cmp); int ed=0; a[ed].x=-1; for(int i=1;i<=n;i++){ if(!equal(a[i],a[ed])) a[++ed]=a[i]; a[ed].ct++; } cdq(1,ed); for(int i=1;i<=ed;i++) ans[a[i].w+a[i].ct]+=a[i].ct; for(int i=1;i<=n;i++) printf("%d\n",ans[i]); }
四维偏序- cdq分治降低三维+排序一维
hdu5126
#include<bits/stdc++.h> using namespace std; const int maxq=5e4+5; struct node{ int w[3],id,ct,type; node()= default; node(int x,int y,int z,int id,int ct,int type):id(id),ct(ct),type(type){ w[0]=x; w[1]=y; w[2]=z; } }; int cmpd; bool sleqt(node a,node b){ for(int i=3-cmpd;i<3;i++) { if(a.w[i]!=b.w[i]) return a.w[i]<b.w[i]; } return a.type<=b.type; } node a[maxq<<3]; int ans[maxq<<3]; int merge(node*a,int n,node*b,int d,int flag){ //assert(b!=a) cmpd=d; int tot=0,mid=n>>1,u=0,v=mid; for(int i=0;i<n;i++){ if(v>=n||(u<mid&&sleqt(a[u],a[v]))){ if(flag||a[u].type==0) b[tot++]=a[u]; u++; } else{ if(flag||a[v].type==1) b[tot++]=a[v]; v++; } } return tot; } //cdq分治三维 void cdq(int d,node*a,int n){//d=3 static node buf[4][maxq<<3]; node*b=buf[d]; if(d==0){ int sum=0; for(int i=0;i<n;i++){ if(a[i].type==0) sum+=a[i].ct; // add else ans[a[i].id]+=sum; // query } }// n==0 n==1 return else if(n>=2){ int mid=n>>1; cdq(d,a,mid),cdq(d,a+mid,n-mid); int tot=merge(a,n,b,d,0); cdq(d-1,b,tot); merge(a,n,b,d,1); for(int i=0;i<n;i++) a[i]=b[i]; } } int qy[maxq][7]; int main(){ int times; scanf("%d",×); while(times--){ int q; scanf("%d",&q); int w[6]; for(int i=0;i<q;i++){ scanf("%d",qy[i]+0); if(qy[i][0]==1) scanf("%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3); else scanf("%d%d%d%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3,qy[i]+4,qy[i]+5,qy[i]+6); } int tot=0; for(int i=0;i<q;i++){ if(qy[i][0]==1) a[tot]=node(qy[i][1],qy[i][2],qy[i][3],tot,1,0),tot++; else { qy[i][1]--,qy[i][2]--,qy[i][3]--; a[tot]=node{qy[i][1],qy[i][2],qy[i][3],tot,1,1},tot++;//0 - a[tot]=node{qy[i][1],qy[i][2],qy[i][6],tot,1,1},tot++;//1 + a[tot]=node{qy[i][1],qy[i][5],qy[i][3],tot,1,1},tot++;//2 + a[tot]=node{qy[i][1],qy[i][5],qy[i][6],tot,1,1},tot++;//3 - a[tot]=node{qy[i][4],qy[i][2],qy[i][3],tot,1,1},tot++;//4 + a[tot]=node{qy[i][4],qy[i][2],qy[i][6],tot,1,1},tot++;//5 - a[tot]=node{qy[i][4],qy[i][5],qy[i][3],tot,1,1},tot++;//6 - a[tot]=node{qy[i][4],qy[i][5],qy[i][6],tot,1,1},tot++;//7 + } } for(int i=0;i<tot;i++) ans[i]=0; cdq(3,a,tot); tot=0; for(int i=0;i<q;i++){ if(qy[i][0]==1) tot++; else{ int*old=ans+tot; printf("%d\n",old[1]+old[2]+old[4]+old[7]-old[0]-old[3]-old[5]-old[6]); tot+=8; } } } }
四维偏序- cdq分治降低两维+排序一维+树状数组一维
#include<bits/stdc++.h> using namespace std; const int maxq=5e4+5; struct node{ int w[3],id,ct,type; node()= default; node(int x,int y,int z,int id,int ct,int type):id(id),ct(ct),type(type){ w[0]=x; w[1]=y; w[2]=z; } }; int cmpd; bool sleqt(node a,node b){ for(int i=3-cmpd;i<3;i++) { if(a.w[i]!=b.w[i]) return a.w[i]<b.w[i]; } return a.type<=b.type; } node a[maxq<<3]; int ans[maxq<<3]; int merge(node*a,int n,node*b,int d,int flag){ //assert(b!=a) cmpd=d; int tot=0,mid=n>>1,u=0,v=mid; for(int i=0;i<n;i++){ if(v>=n||(u<mid&&sleqt(a[u],a[v]))){ if(flag||a[u].type==0) b[tot++]=a[u]; u++; } else{ if(flag||a[v].type==1) b[tot++]=a[v]; v++; } } return tot; } const int B=maxq*6+2; int BIT[B]; //cdq分治两维 void cdq(int d,node*a,int n){//d=3 static node buf[4][maxq<<3]; node*b=buf[d]; if(d==1){ for(int i=0;i<n;i++){ if(a[i].type==0) for(int j=a[i].w[2];j<B;j+=j&-j)BIT[j]+=a[i].ct; // add else for(int j=a[i].w[2];j>0;j-=j&-j)ans[a[i].id]+=BIT[j]; // query } for(int i=0;i<n;i++){ if(a[i].type==0) for(int j=a[i].w[2];j<B;j+=j&-j)BIT[j]-=a[i].ct; // add } }// n==0 n==1 return else if(n>=2){ int mid=n>>1; cdq(d,a,mid),cdq(d,a+mid,n-mid); int tot=merge(a,n,b,d,0); cdq(d-1,b,tot); merge(a,n,b,d,1); for(int i=0;i<n;i++) a[i]=b[i]; } } int qy[maxq][7]; int main(){ int times; scanf("%d",×); while(times--){ vector<int>disc; int q; scanf("%d",&q); int w[6]; for(int i=0;i<q;i++){ scanf("%d",qy[i]+0); if(qy[i][0]==1) { scanf("%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3); for(int j=1;j<=3;j++) disc.push_back(qy[i][j]); } else { scanf("%d%d%d%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3,qy[i]+4,qy[i]+5,qy[i]+6); for(int j=1;j<=6;j++) disc.push_back(qy[i][j]); } } sort(disc.begin(),disc.end()); disc.erase(unique(disc.begin(),disc.end()),disc.end()); int tot=0; for(int i=0;i<q;i++){ if(qy[i][0]==1) { for(int j=1;j<=3;j++) qy[i][j]=lower_bound(disc.begin(),disc.end(),qy[i][j])-disc.begin()+2; a[tot]=node(qy[i][1],qy[i][2],qy[i][3],tot,1,0),tot++; } else { for(int j=1;j<=6;j++) qy[i][j]=lower_bound(disc.begin(),disc.end(),qy[i][j])-disc.begin()+2; qy[i][1]--,qy[i][2]--,qy[i][3]--; a[tot]=node{qy[i][1],qy[i][2],qy[i][3],tot,1,1},tot++;//0 - a[tot]=node{qy[i][1],qy[i][2],qy[i][6],tot,1,1},tot++;//1 + a[tot]=node{qy[i][1],qy[i][5],qy[i][3],tot,1,1},tot++;//2 + a[tot]=node{qy[i][1],qy[i][5],qy[i][6],tot,1,1},tot++;//3 - a[tot]=node{qy[i][4],qy[i][2],qy[i][3],tot,1,1},tot++;//4 + a[tot]=node{qy[i][4],qy[i][2],qy[i][6],tot,1,1},tot++;//5 - a[tot]=node{qy[i][4],qy[i][5],qy[i][3],tot,1,1},tot++;//6 - a[tot]=node{qy[i][4],qy[i][5],qy[i][6],tot,1,1},tot++;//7 + } } for(int i=0;i<tot;i++) ans[i]=0; cdq(3,a,tot); tot=0; for(int i=0;i<q;i++){ if(qy[i][0]==1) tot++; else{ int*old=ans+tot; printf("%d\n",old[1]+old[2]+old[4]+old[7]-old[0]-old[3]-old[5]-old[6]); tot+=8; } } } }
