洛谷P3810 【模板】三维偏序(陌上花开)

    xiaoxiao2022-07-12  175

    D e s c r i p t i o n Description Description

    n n n个元素,每个元素有 a i , b i , c i a_i,b_i,c_i ai,bi,ci三个属性,设 f ( i ) f(i) f(i)表示满足 a j ≤ a i , b j ≤ b i , c j ≤ c i a_j\leq a_i,b_j\leq b_i,c_j\leq c_i ajai,bjbi,cjci j j j的数量,对于 d ∈ [ 0 , n − 1 ] d\in[0,n-1] d[0,n1],求满足 f ( i ) = d f(i)=d f(i)=d的数量


    S o l u t i o n Solution Solution

    经典的三维偏序问题,让我们从最基本的二维偏序开始讲起

    二维偏序就是排序去掉一维,剩下一维树状数组或归并排序( c d q cdq cdq)求逆序对的方法

    现在升级到三维偏序,怎么做呢?

    首先仍然是排序去掉一维,然后下一维 c d q cdq cdq分治套树状数组就解决了,当然也可以 c d q cdq cdq分治再套 c d q cdq cdq

    那能不能树状数组套树状数组呢?空间太大!用 m a p map map多一个 l o g log log,不过你也可以像 c t s c 2019 r k 1 ctsc2019rk1 ctsc2019rk1 r q y rqy rqy大爷那样打一个哈希表,不过这里不推荐

    听说还有平衡树套树状数组?本蒟蒻不会呀QWQ

    P . S : P.S: P.S:由于本题是 ≤ \leq ,所以打树状数组的同学对于 = = =这种情况要特殊处理哦

    时间复杂度? O ( n l o g n l o g k ) ≈ O ( n l o g 2 n ) O(nlognlogk)\approx O(nlog^2n) O(nlognlogk)O(nlog2n)

    等等!!! 根据这个复杂度,貌似 c d q cdq cdq套树状数组的时候不用 O ( n ) O(n) O(n)合并了耶,直接 O ( n l o g n ) O(nlogn) O(nlogn)排序就好了鸭,反正这样的复杂度也是双 l o g log log(懒人专属鸭)


    C o d e Code Code c d q cdq cdq c d q cdq cdq

    #include<cstdio> #include<cctype> #include<algorithm> using namespace std;int ans[100010],n,k,d[100010];//俺觉得俺的代码通俗易懂,所以俺不给俺的代码加注释,等等,好像已经加了QWQ inline long long read() { char c;int d=1;long long f=0; while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } struct node { int x,y,z,*ans;bool b; inline void rd(){x=read();y=read();z=read();return;} inline bool operator ==(const node &a){return x==a.x&&y==a.y&&z==a.z;} }a[100010],b[100010],c[100010]; inline bool cmp(node x,node y){return x.x<y.x||x.x==y.x&&x.y<y.y||x.x==y.x&&x.y==y.y&&x.z<y.z;} inline void cdq2(int l,int r) { if(l==r) return; int mid=l+r>>1; cdq2(l,mid);cdq2(mid+1,r); for(register int i=l,j=l,k=mid+1,cnt=0;i<=r;i++) { if((k>r||b[j].z<=b[k].z)&&j<=mid) c[i]=b[j++],cnt+=c[i].b; else {c[i]=b[k++];if(!c[i].b) *c[i].ans+=cnt;} } for(register int i=l;i<=r;i++) b[i]=c[i]; return; } inline void cdq(int l,int r) { if(l==r) return; int mid=l+r>>1; cdq(l,mid);cdq(mid+1,r); for(register int i=l,j=l,k=mid+1;i<=r;i++) { if((k>r||a[j].y<=a[k].y)&&j<=mid) b[i]=a[j++],b[i].b=1; else b[i]=a[k++],b[i].b=0; } for(register int i=l;i<=r;i++) a[i]=b[i]; cdq2(l,r); return; } signed main() { n=read();k=read(); for(register int i=1;i<=n;i++) a[i].rd(),a[i].ans=&ans[i]; sort(a+1,a+1+n,cmp); for(register int i=n-1;i;i--) if(a[i]==a[i+1]) *a[i].ans=*a[i+1].ans+1; cdq(1,n); for(register int i=1;i<=n;i++) d[ans[i]]++; for(register int i=0;i<n;i++) printf("%d\n",d[i]); }
    最新回复(0)