#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int n,p; int mx,tot; struct node{int a,b,c; }s[maxn*4];//cnt是統(tǒng)計相同的序列數(shù) struct newnode{int a,b,c,cnt,ans; }k[maxn*4]; int c[maxn]; int ljb[maxn]; int lowbit(int x){return x&(-x); } void update(int x,int v){while(x<=p){c[x]+=v;x+=lowbit(x);} } int query(int x){int sum=0;while(x){sum+=c[x];x-=lowbit(x);}return sum; } bool cmp1(node x,node y){if(x.a==y.a){if(x.b==y.b) return x.c<y.c;else return x.b<y.b; } return x.a<y.a; }//第一維的關(guān)鍵字 bool cmp2(newnode x,newnode y){return x.b==y.b?x.c<y.c:x.b<y.b; } void CDQ(int l,int r){if(l==r) return;int mid=(l+r)>>1;CDQ(l,mid);CDQ(mid+1,r);sort(k+l,k+mid+1,cmp2);sort(k+mid+1,k+r+1,cmp2);int i,j=l;//兩個指針 for(i=mid+1;i<=r;i++){while(k[i].b>=k[j].b&&j<=mid){//統(tǒng)計左邊序列 update(k[j].c,k[j].cnt);j++; } k[i].ans+=query(k[i].c);} for(int i=l;i<j;i++){update(k[i].c,-k[i].cnt);} return; } int main(){scanf("%d%d",&n,&p);for(int i=1;i<=n;i++){scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);}sort(s+1,s+1+n,cmp1);//先排第一維for(int i=1;i<=n;i++){//統(tǒng)計重復(fù)元素，去重 tot++;if(s[i].a!=s[i+1].a||s[i].b!=s[i+1].b||s[i].c!=s[i+1].c){k[++mx].a=s[i].a;k[mx].b=s[i].b;k[mx].c=s[i].c;k[mx].cnt=tot;tot=0;}}CDQ(1,mx); for(int i=1;i<=mx;i++){ljb[k[i].ans+k[i].cnt-1]+=k[i].cnt;}for(int i=0;i<n;i++){printf("%d\n",ljb[i]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LJB666/p/11172654.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P3810 【模板】三维偏序（陌上花开） CDQ分治初探的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。