P3810 【模板】三维偏序（陌上花开）

题目背景 这是一道模板题 可以使用bitset，CDQ分治，K-DTree等方式解决。 **** 为了学CDQ分治来做三维偏序。。 什么是CDQ分治呢。。 通俗来讲就是整体二分，把所求问题划为左右两个区间 用左边区间去更新右边区间的答案 对于这道题来说就是先按照第一维a排序 利用CDQ分治，左边区间[l,mid]关于右区间[mid+1,r]就只剩下b和c二维偏序 再来一波“树状数组求逆序对” 就可以求出跨越中线的，用左区间更新右区间的那部分答案 **注意：只计算跨过中线的答案！** 在函数一开始递归处理下去即可 中间用到类似归并的操作 此时左边的a都小于右边的a 那么对于一个右边的元素 之前类似归并的操作就可以保证所有小于b的左边元素都已经被遍历过 那么对于第三维的c，用树状数组/线段树维护一下 归并之后，就发现统计答案完毕之后b是有序递增的了（a已经不重要了） 对于上层操作，符合“左右两边b分别递增”了 听说动态逆序对也可以用CDQ分治（应该比树套树好搞吧） ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=1e5+5; struct flower { int a,b,c,id,siz; friend bool operator < (flower x,flower y) { if (x.b!=y.b) return x.b<y.b; if (x.c!=y.c) return x.c<y.c; return x.id<y.id; } }s[N],t[N<<1],tmp[N<<1]; int n,m,top,belong[N],c[N<<1],f[N<<1],ans[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline int lowbit(int x) { return x&(-x); } inline void add(int x,int k) { while (x<=m) { c[x]+=k; x+=lowbit(x); } } inline void cover(int x,int k) { while (x<=m) { c[x]=k; x+=lowbit(x); } } inline int sum(int x) { int res=0; while (x) { res+=c[x]; x-=lowbit(x); } return res; } void CDQ(int l,int r) { if (l==r) return; int mid=(l+r)>>1; CDQ(l,mid); CDQ(mid+1,r); int p=l,q=mid+1,now=l-1; while (p<=mid&&q<=r) if (t[p]<t[q]) add(t[p].c,t[p].siz),tmp[++now]=t[p++]; else f[t[q].id]+=sum(t[q].c),tmp[++now]=t[q++]; while (p<=mid) tmp[++now]=t[p++]; while (q<=r) f[t[q].id]+=sum(t[q].c),tmp[++now]=t[q++]; for (reg int i=l;i<=r;i++) cover(tmp[i].c,0),t[i]=tmp[i]; } inline bool check(int i) { if (!top) return 0; return (s[i].a==t[top].a&&s[i].b==t[top].b&&s[i].c==t[top].c); } bool cmp(flower x,flower y) { if (x.a!=y.a) return x.a<y.a; if (x.b!=y.b) return x.b<y.b; if (x.c!=y.c) return x.c<y.c; return x.id<y.id; } int main() { n=read(),m=read(); for (reg int i=1;i<=n;i++) { s[i].a=read(),s[i].b=read(),s[i].c=read(); s[i].siz=1,s[i].id=i; } sort(s+1,s+n+1,cmp); for (reg int i=1;i<=n;i++) { if (!check(i)) t[++top]=s[i],t[top].id=top; else ++t[top].siz; belong[i]=top; } CDQ(1,top); for (reg int i=1;i<=top;i++) f[t[i].id]+=t[i].siz-1; for (reg int i=1;i<=n;i++) ++ans[f[belong[i]]]; for (reg int i=0;i<n;i++) printf("%d\n",ans[i]); return 0; } ```