题目链接：https://www.luogu.org/problemnew/show/P3810
题解：三维偏序，cdq分治来解，首先对于首先第一维有序，然后按照一维排序后的第二维二分，树状数组维护第三维。
代码：
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int pp[maxn*2],n,k; int lowbit(int x) { return x&(-x); } void add(int x,int val) { while(x<=k) { pp[x]+=val; x+=lowbit(x); } } int query(int x) { int ans=0; while(x) { ans+=pp[x]; x-=lowbit(x); } return ans; } struct node { int a,b,c,siz,mm; }s[maxn]; int cmp(node p,node q) { if(p.a==q.a&&p.b==q.b) return p.c<q.c; else if(p.a==q.a) return p.b<q.b; else return p.a<q.a; } int cmp1(node p,node q) { if(p.b==q.b) return p.c<q.c; else return p.b<q.b; } void solve(int l,int r) { if(l==r) {s[l].mm+=(s[l].siz-1);return ;} int mid=(l+r)>>1; solve(l,mid);solve(mid+1,r); sort(s+l,s+1+mid,cmp1);sort(s+mid+1,s+r+1,cmp1); int j=l; for(int i=mid+1;i<=r;i++) { while(j<=mid&&s[j].b<=s[i].b) add(s[j].c,s[j].siz),j++; s[i].mm+=query(s[i].c); } for(int i=l;i<j;i++) add(s[i].c,-s[i].siz); } int sum[maxn]; int main() { scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d %d %d",&s[i].a,&s[i].b,&s[i].c);s[i].siz=s[i].mm=0; } sort(s+1,s+1+n,cmp); int ans=1,xx=1; for(int i=2;i<=n;i++) { if(s[i].a==s[i-1].a&&s[i].b==s[i-1].b&&s[i].c==s[i-1].c) ans++; else { s[xx].siz=ans; s[++xx]=s[i]; ans=1; } } s[xx].siz=ans; solve(1,xx); for(int i=1;i<=xx;i++) sum[s[i].mm]+=s[i].siz; for(int i=0;i<=n-1;i++) printf("%d\n",sum[i]); return 0; }
