题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3262
第一道CDQ分治题！
看博客：https://www.cnblogs.com/Narh/p/9230515.html
CDQ分治意外地很好写啊，而且好厉害！膜拜CDQ！
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const maxn=1e5+5,maxm=2e5+5; int n,m,f[maxm],ans[maxn],tot; struct N{int a,b,c,sum,num;}s[maxn],t[maxn]; bool cmp(N x,N y){return (x.a<y.a) || (x.a==y.a && x.b<y.b) || (x.a==y.a && x.b==y.b && x.c<y.c);} bool cmp2(N x,N y){return x.b<y.b;} bool ck(N x,N y){return (x.a==y.a) && (x.b==y.b) && (x.c==y.c);} void add(int x,int v){for(;x<=m;x+=(x&-x))f[x]+=v;}// <=m 而非 <=n ! int query(int x){int ret=0; for(;x;x-=(x&-x))ret+=f[x]; return ret;} void cdq(int l,int r) { if(l==r)return; int mid=((l+r)>>1); cdq(l,mid); cdq(mid+1,r); sort(t+l,t+mid+1,cmp2); sort(t+mid+1,t+r+1,cmp2); int p=l; for(int i=mid+1;i<=r;i++) { while(p<=mid && t[p].b<=t[i].b)add(t[p].c,t[p].num),p++;// <= t[i].sum+=query(t[i].c); } for(int i=l;i<p;i++)add(t[i].c,-t[i].num);//撤销 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c); sort(s+1,s+n+1,cmp); for(int i=1,cnt;i<=n;i++) { cnt=1; while(ck(s[i],s[i+1]))cnt++,i++; t[++tot]=s[i]; t[tot].num=cnt; } cdq(1,tot); for(int i=1;i<=tot;i++)ans[t[i].sum+t[i].num-1]+=t[i].num; for(int i=0;i<n;i++)printf("%d\n",ans[i]); return 0; }