三维偏序
P3810 【模板】三维偏序(陌上花开)题目背景这是一道模板题 可以使用bitset,CDQ分治,K-DTree等方式解决。 题目描述有(n)个元素,第(i)个元素有(a_i)、(b_i)、(c_i)三个属性,设(f(i))表示满足(a_j leq a_i)且(b_j leq b_i)且(c_j leq c_i)的(j)的数量。 对于(d in [0,n)),求(f(i)=d)的数量 输入输出格式输入格式:第一行两个整数(n)、(k),分别表示元素数量和最大属性值。 之后(n)行,每行三个整数(a_i) 、(b_i)、(c_i),分别表示三个属性值。 输出格式:输出(n)行,第(d+1)行表示(f(i)=d)的(i)的数量。 说明$1 leq n leq 100000,1 leq k leq 200000 $ 这里采用的是归并排序套树状数组的做法。 先不考虑重复元素 首先考虑二维偏序,我们可以对二元组((x,y))以(x)为第一关键字,(y)为第二关键字进行排序。然后单独讨论(y)的顺序对(与逆序对相反的一个概念),每个(y)的顺序对数量即为满足题目条件的顺序对数量。这点不难想明白。 然后类比三维偏序,我们可以对三元组((x,y,z))同样如此做,但统计时并不是(y)的所有顺序对都合法,我们对统计时的(z)维护一权值树状数组,每次查询在顺序对中有多少个(z)小于等于当前的(z)的 考虑重复元素,这个题题意没有明确说明,但每个三元组是不考虑自己的。 我们先缩点去重,然后统计的时候按数量统计即可 Code: #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=100010; const int M=200010; struct node { int x,z,cnt; bool friend operator <(node n1,node n2) { if(n1.x==n2.x) { if(n1.y==n2.y) return n1.z<n2.z; return n1.y<=n2.y; } return n1.x<n2.x; } }a[N],d[N],dx[N],tmp[N]; int n,n_,k; void init() { scanf("%d%d",&n_,&k); for(int i=1;i<=n_;i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].cnt=1; } sort(a+1,a+1+n_); for(int i=1;i<=n_;i++) { while(d[n].x==a[i].x&&d[n].y==a[i].y&&d[n].z==a[i].z) d[n].cnt++,i++; if(i<=n_) d[++n]=a[i]; } } int sum[M],ans[N],cnt0[N]; void add(int x,int delta) { while(x<=k) { sum[x]+=delta; x+=x&-x; } } int query(int x) { int s=0; while(x) { s+=sum[x]; x-=x&-x; } return s; } void divide(int l,int r) { if(l==r) {cnt0[l]+=dx[l].cnt-1;return;} int mid=l+r>>1; divide(l,mid); divide(mid+1,r); int pos=l,cnt=l-1; for(int i=mid+1;i<=r;i++) { while(pos<=mid&&dx[pos]<dx[i]) { tmp[++cnt]=dx[pos]; add(dx[pos].y,dx[pos].cnt); pos++; } tmp[++cnt]=dx[i],cnt0[dx[i].z]+=query(dx[i].y); } for(int i=l;i<pos;i++) add(dx[i].y,-dx[i].cnt); while(pos<=mid) tmp[++cnt]=dx[pos++]; for(int i=l;i<=r;i++) dx[i]=tmp[i]; } void work() { for(int i=1;i<=n;i++) dx[i].x=d[i].y,dx[i].y=d[i].z,dx[i].z=i,dx[i].cnt=d[i].cnt; divide(1,n); for(int i=1;i<=n;i++) { for(int j=1;j<=dx[i].cnt;j++) ans[cnt0[dx[i].z]]++; } for(int i=0;i<n_;i++) printf("%dn",ans[i]); } int main() { init(); work(); return 0; } 2018.7.15 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |