并不对劲的cdq分治

这并不是对劲的cdq分治…… 如果想看更不对劲的，点这里-> [:-)](http://www.cnblogs.com/xzyf/p/8466293.html) cdq分治每次计算前一半对后一半的影响。具体地， 假设三维分别是x,y,z，先按x排序。分治时每次将前半边、后半边分别按y排序。虽然现在x的顺序被打乱了，但是前半边还是都小于后半边的，所以要是只计算前半边对后半边的偏序关系，是不会受到x的影响的。维护后一半的指针i，前一半的指针j，每次将i后移一位时，若y[j]<=y[i]则不断后移j，并不断将z[j]加入树状数组。然后再查询树状数组中有多少数小于等于z[i]。 最后要清空树状数组。 它有那么一些些眼熟，解一维偏序时就是归什么排序。 ```cpp #include<iostream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #define maxn 100010 #define maxk 200010 #define ll long long using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } inline void write(int x) { int f=0;char ch[20]; if(!x){puts("0");return;} if(x<0){putchar('-');x=-x;} while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n'); } typedef struct node { int x,y,z,ans,w; }stnd; stnd a[maxn],b[maxn]; int n,cnt[maxk]; int k,n_; bool cmpx(stnd u,stnd v) { if(u.x==v.x) { if(u.y==v.y) return u.z<v.z; return u.y<v.y; } return u.x<v.x; } bool cmpy(stnd u,stnd v) { if(u.y==v.y) return u.z<v.z; return u.y<v.y; } struct treearray { int tre[maxk],kk; int lwbt(int x){return x&(-x);} int ask(int i){int ans=0; for(;i;i-=lwbt(i))ans+=tre[i];return ans;} void add(int i,int k){for(;i<=kk;i+=lwbt(i))tre[i]+=k;} }t; void cdq(int l,int r) { if(l==r)return; int mid=(l+r)>>1; cdq(l,mid);cdq(mid+1,r); sort(a+l,a+mid+1,cmpy); sort(a+mid+1,a+r+1,cmpy); int i=mid+1,j=l; for(;i<=r;i++) { while(a[j].y<=a[i].y && j<=mid) t.add(a[j].z,a[j].w),j++; a[i].ans+=t.ask(a[i].z); } for(i=l;i<j;i++) t.add(a[i].z,-a[i].w); } int main() { n_=read(),k=read();t.kk=k; for(int i=1;i<=n_;i++) b[i].x=read(),b[i].y=read(),b[i].z=read(); sort(b+1,b+n_+1,cmpx); int c=0; for(int i=1;i<=n_;i++) { c++; if(b[i].x!=b[i+1].x || b[i].y!=b[i+1].y || b[i].z!=b[i+1].z ) a[++n]=b[i],a[n].w=c,c=0; } cdq(1,n); for(int i=1;i<=n;i++) cnt[a[i].ans+a[i].w-1]+=a[i].w; for(int i=0;i<n_;i++) write(cnt[i]); return 0; } ```