Description

小Y家里有一個(gè)大森林，里面有n棵樹，編號(hào)從1到n。一開始這些樹都只是樹苗，只有一個(gè)節(jié)點(diǎn)，標(biāo)號(hào)為1。這些樹
都有一個(gè)特殊的節(jié)點(diǎn)，我們稱之為生長(zhǎng)節(jié)點(diǎn)，這些節(jié)點(diǎn)有生長(zhǎng)出子節(jié)點(diǎn)的能力。小Y掌握了一種魔法，能讓第l棵樹
到第r棵樹的生長(zhǎng)節(jié)點(diǎn)長(zhǎng)出一個(gè)子節(jié)點(diǎn)。同時(shí)她還能修改第l棵樹到第r棵樹的生長(zhǎng)節(jié)點(diǎn)。她告訴了你她使用魔法的
記錄，你能不能管理她家的森林，并且回答她的詢問呢？

Solution

有點(diǎn)神仙,看了題解的做法
首先顯然要離線,否則空間都是錯(cuò)的,這樣維護(hù)一棵樹就好了
然后發(fā)現(xiàn)都是區(qū)間修改,掃描線維護(hù)一下節(jié)點(diǎn)就好了
但是還有刪除節(jié)點(diǎn)這樣的操作,復(fù)雜度保證不了

不如先把樹的形態(tài)都建出來,對(duì)于 \(1\) 到 \(n\) 的公共部分我們一起考慮,不同的部分就直接新建節(jié)點(diǎn)
考慮維護(hù)添加,刪除操作的復(fù)雜度
我們每產(chǎn)生一個(gè)新的生長(zhǎng)節(jié)點(diǎn)就新建一個(gè)虛點(diǎn),然后把新長(zhǎng)出來的都接上去
如果按加入時(shí)間考慮的話,有很多連續(xù)的節(jié)點(diǎn)都是同一個(gè)父親,所以我們用一個(gè)虛點(diǎn)暫時(shí)代替它們的父親
然后對(duì)于 \(1\) 到 \(n\) 的不同的樹,它們的父親是不一樣的,因?yàn)榻⒘诉@個(gè)虛點(diǎn),所以只需要把虛點(diǎn)的父親變一下,就可以達(dá)到把所有的點(diǎn)的父親都改變的效果了

具體的也說不清楚,看代碼比較直觀.....

#include<bits/stdc++.h> using namespace std; template<class T>void gi(T &x){int f;char c;for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f; } const int N=4e5+10; int n,m,ch[N][2],fa[N],a[N],w[N]; inline void upd(int x){w[x]=w[ch[x][0]]+w[ch[x][1]]+a[x];} inline bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} inline void rotate(int x){int y=fa[x];bool t=ch[y][1]==x;ch[y][t]=ch[x][!t];fa[ch[y][t]]=y;ch[x][!t]=y;fa[x]=fa[y];if(!isrt(y))ch[fa[y]][ch[fa[y]][1]==y]=x;fa[y]=x;upd(y);upd(x); } inline void splay(int x){while(!isrt(x)){int y=fa[x],p=fa[y];if(isrt(y))rotate(x);else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);else rotate(x),rotate(x);} } inline int access(int x){int y=0;while(x)splay(x),ch[x][1]=y,upd(x),x=fa[y=x];return y; } inline void link(int x,int y){access(x);splay(x);fa[x]=y; } inline void cut(int x){access(x);splay(x);fa[ch[x][0]]=0;ch[x][0]=0;upd(x); } inline int query(int x,int y){int ret=0,t;access(x);splay(x);ret+=w[x];t=access(y);splay(y);ret+=w[y];access(t);splay(t);ret-=w[t]<<1;return ret; } int L[N],R[N],id[N],cnt=2,ans[N],top=0; struct data{int ty,p,x,y;inline bool operator <(const data &t)const{if(p!=t.p)return p<t.p;return ty<t.ty;} }q[N]; int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);cin>>n>>m;int op,l,r,x,y=2,tp=0,ID=1;L[1]=1;R[1]=n;id[1]=1;w[1]=a[1]=1;L[2]=1;R[2]=n;w[2]=a[2]=0;link(2,1);for(int i=1;i<=m;i++){gi(op);gi(l);gi(r);if(op==0){a[++cnt]=1;w[cnt]=1;L[++ID]=l;R[ID]=r;id[ID]=cnt;link(cnt,y);}else if(op==1){gi(x);a[++cnt]=0;w[cnt]=0;l=max(l,L[x]);r=min(r,R[x]);if(l<=r){link(cnt,y);q[++top]=(data){-1,l,cnt,id[x]};q[++top]=(data){-1,r+1,cnt,y};y=cnt;}}else gi(x),q[++top]=(data){++tp,l,id[r],id[x]};}sort(q+1,q+top+1);for(int i=1,j=1;i<=n;i++){while(j<=top && q[j].p==i){if(q[j].ty==-1)cut(q[j].x),link(q[j].x,q[j].y);else ans[q[j].ty]=query(q[j].x,q[j].y);j++;}}for(int i=1;i<=tp;i++)printf("%d\n",ans[i]);return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的bzoj 4573: [Zjoi2016]大森林的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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