《P3810 【模板】三维偏序 / 陌上花开》

题目背景

这是一道模板题，可以使用 bitset，CDQ 分治，树套树，KD-Tree 等方式解决。

题目描述

有 n 个元素，第 i 个元素有 ai​,bi​,ci​ 三个属性，设 f(i) 表示满足 aj​≤ai​ 且 bj​≤bi​ 且 cj​≤ci​ 且 j=i 的 j 的数量。

对于所有 d∈[0,n)，求 f(i)=d 的数量。

输入格式

第一行两个整数 n,k，表示元素数量和最大属性值。

接下来 n 行，每行三个整数 ai​,bi​,ci​，分别表示三个属性值。

输出格式

共 n 行，第 d+1 行表示 f(i)=d 的 i 的数量。

输入输出样例

输入 #1复制

10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1

输出 #1复制

3 1 3 0 1 0 1 0 0 1

说明/提示

对于所有数据，保证 1≤n≤105，1≤ai​,bi​,ci​≤k≤2×105。

代码实现：

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=1e5+10; int n,m,tn; int sz[N],res[N],cnt[N],tr[2*N]; struct nd { int x,y,z; int id; bool operator != (const nd &t) const { return (x!=t.x||y!=t.y||z!=t.z); } }inp[N],dat[N],tmp[N]; inline int lowbit(int x) { return x&(-x); } inline void upd(int x,int c) { for(int i=x;i<=m;i+=lowbit(i)) tr[i]+=c; } inline int qry(int x) { int s=0; for(int i=x;i>=1;i-=lowbit(i)) s+=tr[i]; return s; } inline void cdq(int l,int r) { if(l==r) return; int mid=(l+r)/2,p=l,q=mid+1; cdq(l,mid),cdq(mid+1,r); for(int i=l;i<=r;i++) { if((p<=mid&&dat[p].y<=dat[q].y)||q>r) upd(dat[p].z,sz[dat[p].id]),tmp[i]=dat[p++]; else res[dat[q].id]+=qry(dat[q].z),tmp[i]=dat[q++]; } for(int i=l;i<=mid;i++) upd(dat[i].z,-sz[dat[i].id]); for(int i=l;i<=r;i++) dat[i]=tmp[i]; } inline bool cmp(nd a, nd b) { if(a.x==b.x) { if(a.y==b.y) return a.z<b.z; else return a.y<b.y; } else return a.x<b.x; } int main() { scanf("%d%d",&tn,&m); for(int i=1;i<=tn;i++) scanf("%d%d%d",&inp[i].x,&inp[i].y,&inp[i].z); sort(inp+1,inp+tn+1,cmp); for(int i=1;i<=tn;i++) { if(inp[i]!=inp[i-1]) dat[++n]=inp[i],dat[n].id=n; sz[n]++; } cdq(1,n); for(int i=1;i<=n;i++) cnt[res[dat[i].id]+sz[dat[i].id]-1]+=sz[dat[i].id]; for(int i=0;i<tn;i++) printf("%d\n",cnt[i]); return 0; }