「ZJOI2016」大森林

神仙題...

很顯然線段樹搞不了

考慮離線操作

我們只搞一顆樹，從位置1一直往后移動，然后維護它的形態試試

顯然操作0,1都可以拆成差分的形式，就是加入和刪除

因為保證了操作2的合法性，我們不妨先不計合法性把所有點加到樹中

顯然每個點要連到在這個點之前的離這個點時間上最近那個1操作的點上

然后可以發現移動時1操作相當于很多個點換根

我們可以對每個1操作建一個虛點，然后就可以很方便換根了

那么如何保證查詢操作呢？

可以把每個1操作的虛點大小設成0(代表它父親邊的直接長度)，并按時間串起來。

這樣，一個虛點的虛點兒子的子樹的點其實也是它的子樹了，查詢的時候差dis[u]+dis[v]-dis[lca]*2就可以了

是不是以為這個0操作的區間限制就沒有用了？

其實不是，注意到1操作的點可能還沒出現...這時候就要把1操作刪掉

---

Code:

#include <cstdio> #include <cctype> #include <algorithm> using std::min; using std::max; const int N=3e5+10; template <class T> void read(T &x) {x=0;char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar(); } int ans[N],n,m,_n,_m,q,p[N],node,ti[N],tot,L[N],R[N]; struct koito_yuu {int pos,op,u,v;koito_yuu(){}koito_yuu(int Pos,int Op,int U,int V){pos=Pos,op=Op,u=U,v=V;}bool friend operator <(koito_yuu a,koito_yuu b){return a.pos==b.pos?a.op<b.op:a.pos<b.pos;} }yuu[N]; #define ls ch[now][0] #define rs ch[now][1] #define fa par[now] int sum[N],ch[N][2],par[N],siz[N]; bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;} int identity(int now){return ch[fa][1]==now;} void connect(int f,int now,int typ){ch[fa=f][typ]=now;} void updata(int now){sum[now]=sum[ls]+sum[rs]+siz[now];} void Rotate(int now) {int p=fa,typ=identity(now);connect(p,ch[now][typ^1],typ);if(isroot(p)) connect(par[p],now,identity(p));else fa=par[p];connect(now,p,typ^1);updata(p),updata(now); } void splay(int now) {for(;isroot(now);Rotate(now))if(isroot(fa))Rotate(identity(now)^identity(fa)?now:fa); } int access(int now) {int las=0;for(;now;las=now,now=fa) splay(now),rs=las,updata(now);return las; } int LCA(int x,int y) {access(x);return access(y); } void link(int x,int y) {access(x),splay(x);par[x]=y; } void cat(int x) {access(x),splay(x);par[ch[x][0]]=0;ch[x][0]=0; } int qry(int x) {access(x),splay(x);return sum[x]; } int query(int x,int y) {int lca=LCA(x,y);return qry(x)+qry(y)-(qry(lca)<<1); } int main() {read(n),read(m);L[1]=1,R[1]=n,node=1,++tot;for(int op,l,r,x,u,v,i=1;i<=m;i++){read(op);if(op==0) ++node,read(L[node]),read(R[node]),p[node]=i;else if(op==1){ti[++tot]=i;link(tot,tot-1);read(l),read(r),read(x);l=max(L[x],l),r=min(R[x],r);if(l>r) continue;yuu[++q]=koito_yuu(l,-1,x,tot);yuu[++q]=koito_yuu(r+1,0,x,tot);}else{read(x),read(u),read(v);yuu[++q]=koito_yuu(x,++_n,u,v);}}_m=tot;for(int i=2;i<=node;i++){int pos=std::upper_bound(ti+1,ti+1+_m,p[i])-ti-1;siz[++tot]=1,sum[tot]=1;link(tot,pos);}std::sort(yuu+1,yuu+1+q);for(int j=1,i=1;i<=n;i++){while(yuu[j].pos==i){int u=yuu[j].u+_m-1,v=yuu[j].v;if(u==_m) u=1;if(yuu[j].op==-1){cat(v);link(v,u);}else if(yuu[j].op==0){cat(v);link(v,v-1);}else ans[yuu[j].op]=query(u,v==1?1:v+_m-1);++j;}}for(int i=1;i<=_n;i++) printf("%d\n",ans[i]);return 0; }

---

2019.3.11

轉載于:https://www.cnblogs.com/butterflydew/p/10513710.html

總結

以上是生活随笔為你收集整理的「ZJOI2016」大森林 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。