注意判斷 三個(gè)條件都一樣的……
（CDQ分治 其實(shí)并不是很難理解 只是想不到……）

CDQ分治：

//By SiriusRen #include <cstdio> #include <algorithm> using namespace std; #define N 888888 int n,k,tree[N],tot,ans[N]; struct Node{int a,b,c,ans,sum;}node[N]; bool cmp(Node a,Node b){if(a.a!=b.a)return a.a<b.a;if(a.b!=b.b)return a.b<b.b;return a.c<b.c;} bool cmp2(Node a,Node b){return a.b<b.b;} void insert(int l,int r,int pos,int num,int wei){if(l==r){tree[pos]+=wei;return;}int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;if(mid>=num)insert(l,mid,lson,num,wei);else insert(mid+1,r,rson,num,wei);tree[pos]=tree[lson]+tree[rson]; } int query(int l,int r,int pos,int num){if(r<=num)return tree[pos];int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;if(mid>=num)return query(l,mid,lson,num);else return query(l,mid,lson,num)+query(mid+1,r,rson,num); } void cdq(int l,int r){if(l==r)return;int mid=(l+r)>>1,jy=l;cdq(l,mid),cdq(mid+1,r);sort(node+l,node+mid+1,cmp2),sort(node+mid+1,node+r+1,cmp2);for(int i=mid+1;i<=r;i++){while(jy<=mid&&node[jy].b<=node[i].b)insert(1,k,1,node[jy].c,node[jy].sum),jy++;node[i].ans+=query(1,k,1,node[i].c);}while(jy-->l)insert(1,k,1,node[jy].c,-node[jy].sum); } int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;node[i].sum=1,i++)scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);sort(node+1,node+1+n,cmp);for(int i=1;i<=n;i++)if(node[i].a!=node[tot].a||node[i].b!=node[tot].b||node[i].c!=node[tot].c)node[++tot]=node[i];else node[tot].sum++;cdq(1,tot);for(int i=1;i<=tot;i++)ans[node[i].ans+node[i].sum-1]+=node[i].sum;for(int i=0;i<n;i++)printf("%d\n",ans[i]); }

樹套樹 （線段樹+treap）：

//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 6005000 int n,k,root[N],size,t,ans,rec,Ans[1000500]; struct Node{int s,c,m;}node[1000500]; struct Tree{int ch[2],v,cnt,rnd,sz;}tr[N]; bool cmp(Node a,Node b){if(a.s!=b.s)return a.s<b.s;if(a.c!=b.c)return a.c<b.c;return a.m<b.m;} void Upd(int k){tr[k].sz=tr[k].cnt+tr[tr[k].ch[0]].sz+tr[tr[k].ch[1]].sz;} void rot(int &k,bool f){int t=tr[k].ch[f];tr[k].ch[f]=tr[t].ch[!f],tr[t].ch[!f]=k,Upd(k),Upd(t),k=t;} void ins(int &k,int num){if(!k){k=++size;tr[k].cnt=tr[k].sz=1,tr[k].rnd=rand(),tr[k].v=num;return;}tr[k].sz++;if(tr[k].v==num){tr[k].cnt++;return;}bool f=num>tr[k].v;ins(tr[k].ch[f],num);if(tr[k].rnd>tr[tr[k].ch[f]].rnd)rot(k,f); } void ask(int &k,int num){if(!k)return;if(tr[k].v==num){ans+=tr[k].cnt+tr[tr[k].ch[0]].sz; return;}else if(tr[k].v>num)ask(tr[k].ch[0],num);else ans+=tr[k].cnt+tr[tr[k].ch[0]].sz,ask(tr[k].ch[1],num); } void Insert(int l,int r,int pos){ins(root[pos],node[t].m);if(l==r)return;int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;if(mid<node[t].c)Insert(mid+1,r,rson);else Insert(l,mid,lson); } void Query(int l,int r,int pos){if(r<=node[t].c){ask(root[pos],node[t].m);return;}int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;if(mid>=node[t].c)Query(l,mid,lson);else Query(l,mid,lson),Query(mid+1,r,rson); } int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d%d%d",&node[i].s,&node[i].c,&node[i].m);sort(node+1,node+1+n,cmp);for(t=1;t<=n;t++){if(node[t].c!=node[t+1].c||node[t].m!=node[t+1].m||node[t].s!=node[t+1].s)ans=0,Query(1,k,1),Ans[ans]+=rec+1,Insert(1,k,1),rec=0;else rec++,Insert(1,k,1);}for(int i=0;i<n;i++)printf("%d\n",Ans[i]); }

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

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3262 cdq分治 OR 树套树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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