正題

題目鏈接:https://www.luogu.com.cn/problem/P3810

---

題目大意

$n$個(gè)三元組$(a,b,c)$，$$f(i)=\sum _{i=1}^{n,j=i}[a_j\le a_i\&b_j\le b_i\&b_j\le b_i]$$

對(duì)于每個(gè)$d$，求有多少個(gè)$f(i)=d$

---

解題思路

先按照$a$排序，然后對(duì)于$b$這一維進(jìn)行$CDQ$分治，之后用樹狀數(shù)組計(jì)算$c$這一維的結(jié)果即可。

要注意的是統(tǒng)計(jì)$f(i)$的時(shí)候要在結(jié)構(gòu)體里，不然它不會(huì)隨著排序而交換。

時(shí)間復(fù)雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; struct node{int a,b,c,w,ans; }a[N],b[N]; int n,m,k,ask[N]; struct Tree_Array{#define lowbit(x) (x&-x)int t[N];void Change(int x,int z){while(x<=k){t[x]+=z;x+=lowbit(x);}}int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;}#undef lowbit(x) }Ta; bool Cmp(node x,node y){if(x.a!=y.a) return x.a<y.a;return (x.b==y.b)?(x.c<y.c):(x.b<y.b); } bool cMp(node x,node 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(a+l,a+mid+1,cMp);sort(a+mid+1,a+r+1,cMp);int k=l;for(int i=mid+1;i<=r;i++){while(k<=mid&&a[k].b<=a[i].b)Ta.Change(a[k].c,a[k].w),k++;a[i].ans+=Ta.Ask(a[i].c);}for(int i=l;i<k;i++)Ta.Change(a[i].c,-a[i].w);return; } int main() {scanf("%d%d",&m,&k);for(int i=1;i<=m;i++)scanf("%d%d%d",&b[i].a,&b[i].b,&b[i].c);sort(b+1,b+1+m,Cmp);for(int i=1,c=0;i<=m;i++){c++;if(b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c)a[++n]=b[i],a[n].w=c,c=0;}Cdq(1,n);for(int i=1;i<=n;i++)ask[a[i].ans+a[i].w-1]+=a[i].w;for(int i=0;i<m;i++)printf("%d\n",ask[i]); }

總結(jié)

以上是生活随笔為你收集整理的P3810-[模板]三维偏序(陌上花开)【CDQ分治,树状数组】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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