传送门
“CDQ分治”从来都没有听说过，写了这题才知道还有这么神奇的算法。
（被逼无奈）。w(ﾟДﾟ)w
于是看了不少dalao的博客，对CDQ算法粗浅地了解了一点。（想要了解CDQ的概念，可以看下这位dalao的博客）
所以，这道题要怎么做呢。。。
根据，CDQ分治理论，这题按照题意建出来储存信息的数组很明显是个三维的。很巧的是，CDQ分治的好处之一就是降维（根据官方民间说法,每降一维要付出一个log的时间代价）。则本题的三维数组，根据CDQ就有：第一维用来直接排序，第二维做CDQ分治，第三维做树状数组。
为了能够更加透彻地理解此题思路，借鉴了洛谷dalao的题解。
【解题思路】
- 这题有很多解法碰巧我们是作为CDQ分治的例题，于是这里就只介绍CDQ分治的解法
- 一道三维偏序，所以先把所有属性进行多关键字排序，先按a排序，再按b排序，最后按c排序，这就保证了在数列里面，后面的a会比前面的a要大（相当于把a离散化）。
- 接着就进行CDQ分治，对于一个区间l到r来说，a是已经排好序的。在CDQ分治完l--mid和mid+1--r这两个区间后，把l到r进行多关键字排序，这次先按b排序，再按c排序，最后按a排序，这就再保证了b的要求。
- 然后像CDQ分治需要的那样，把小于等于mid的a的贡献统计起来，把1-c的区间全部加1，优化大于mid的值的答案。这是一个区间修改，单点查询的操作，可以用线段树或者树状数组解决，本人为了方便用了树状数组。
- 记得最后还原树状数组。注意，如果直接对整个数组进行memset有可能会超时，我们只需对直接的操作进行反操作，把小于等于mid的a中，1-c的区间全部加-1即可。
- 最后进行判重（为什么要判重呢？因为如果有几个相同的量，我们CDQ分治的时候并没有管它，直接计算就会把所有结果都计算出来。这是你如果不判重，那么就会把一个答案反复累加，最终答案就会变大）
——摘自洛谷题解
那么融合了各位dalao的CDQ精华，以及本蒟蒻对CDQ的理解（+注释）后，就有了AC的极简代码。
#include<algorithm> #include<cstdio> using namespace std; #define maxn 100005 struct node{int x,y,z,num,ans;}a[maxn]; int n,m,tot,ans[maxn],sum[maxn<<2]; inline bool cmp2(const node&a,const node&b) { if(a.y!=b.y) return a.y<b.y; return a.z<b.z; } inline bool cmp1(const node&a,const node&b) { if(a.x!=b.x) return a.x<b.x; return cmp2(a,b); } inline void Add(int x,int y)//极简的树状数组 { for(;x<=m;x+=x&(-x)) sum[x]+=y; } inline int Quary(int x)//合并左右子区间的贡献 { int ans=0; for(;x;x-=x&(-x)) ans+=sum[x]; return ans; } inline 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,cmp2); sort(a+mid+1,a+r+1,cmp2);//把两个子问题的第一维分别进行排序。 for(int i=mid+1,j=l;i<=r;i++) { while(j<=mid&&a[j].y<=a[i].y) //若第二维的左子区间的a[j].y对右子区间产生了贡献 Add(a[j].z,a[j].num),j++;//就把第三维的a[j].z扔进树状数组 a[i].ans+=Quary(a[i].z);//归并排序 } for(int i=l,max=a[r].y;i<=mid&&a[i].y<=max;i++) Add(a[i].z,-a[i].num);//清空树状数组（作案不留痕迹） } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+n+1,cmp1);//按第一维排序 for(int i=1;i<=n;i++,a[tot].num++) if(a[i].x!=a[tot].x||a[i].y!=a[tot].y||a[i].z!=a[tot].z) a[++tot]=a[i];//把可以符合题意的x,y,z先找出来，同时统计个数（分别）（相当于去重） CDQ(1,tot);//进行CDQ分治 for(int i=1;i<=tot;i++) ans[a[i].ans+a[i].num-1]+=a[i].num;//把重复的加回来 for(int i=0;i<n;i++) printf("%d ",ans[i]); return 0; }