bzoj 4573
LCT神題...
首先暴力的做法就是每次在一個區間上link，然后暴力查詢，時間復雜度$O(爆炸)$
但是我們可以發現的是，每棵樹之間互不影響！
因此我們可以考慮離線之后分別統計每棵樹
但是這樣做其實并沒有優化時空啊！
但是等等，我們在考慮一下：我們的操作都是區間操作，也就是說我們可以用一個類似差分的思想，一棵樹一棵樹地處理，處理到區間端點的時候修改一些東西就行了！
那么更換生長節點怎么辦？
我們建立一個虛點表示生長節點，然后把新產生的點都連到這個點上就行
于是思路就順理成章了：
對于新建節點的操作，我們新生成一個點權為1的節點，記錄下這個節點生效的區間，然后把他掛到現在的生長節點上
對于更換生長節點的操作，我們新建一個點權為0的節點，將讀入的區間與這個點生效的區間取交集作為有效的區間，在這個區間左端點把他掛在要求的實際節點上，右端點掛回虛節點鏈上
對于查詢操作，直接用LCA查詢即可，求LCA的方法見代碼中access函數
然后離線所有操作，先按樹的標號排序（注意新建節點的操作都認為是第一棵樹上的，這樣后面才能產生足夠的節點去移動），先進行修改再進行查詢（可以在排序時通過正負把查詢排到后面）
這樣問題就解決了
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; struct Ques { int pos,typ; int x,y; Ques (){} Ques (int a,int b,int c,int d):pos(a),typ(b),x(c),y(d){} friend bool operator < (Ques a,Ques b) { return a.pos==b.pos?a.typ<b.typ:a.pos<b.pos; } }q[400005]; int ch[400005][2]; int siz[400005],f[400005],val[400005]; int ret[400005]; int fl[400005],fr[400005]; int lq[400005],rq[400005]; int n,m,Q; int tot=0,cnt=0,ttop=0; void update(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+val[x]; } bool be_root(int x) { if(ch[f[x]][0]==x||ch[f[x]][1]==x)return 0; return 1; } void rotate(int x) { int y=f[x],z=f[y],k=(ch[y][1]==x); if(!be_root(y))ch[z][ch[z][1]==y]=x; f[x]=z; ch[y][k]=ch[x][!k],f[ch[x][!k]]=y; ch[x][!k]=y,f[y]=x; update(y),update(x); } void splay(int x) { while(!be_root(x)) { int y=f[x],z=f[y]; if(!be_root(y)) { if((ch[z][1]==y)^(ch[y][1]==x))rotate(x); else rotate(y); } rotate(x); } //update(x); } int access(int x) { int y=0; while(x) { splay(x); ch[x][1]=y; update(x); y=x,x=f[x]; } return y; } void link(int x,int y) { splay(x),f[x]=y; } void cut(int x) { access(x),splay(x),f[ch[x][0]]=0,ch[x][0]=0,update(x); } void new_node(int x) { tot++,val[tot]=siz[tot]=x; } int query(int x,int y) { int ret=0,fa; access(x),splay(x),ret+=siz[x]; fa=access(y),splay(y),ret+=siz[y]; access(fa),splay(fa),ret-=2*siz[fa]; return ret; } inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(),m=read(); new_node(1),new_node(0); cnt=1,lq[1]=fr[1]=1,rq[1]=n; int las=2;link(2,1); for(int i=1;i<=m;i++) { int t=read(); if(!t) { int l=read(),r=read(); new_node(1); lq[++cnt]=l,rq[cnt]=r,fr[cnt]=tot; q[++ttop]=Ques(1,i-m,tot,las); }else if(t==1) { int l=read(),r=read(),x=read(); l=max(l,lq[x]),r=min(r,rq[x]); if(l<=r) { new_node(0),link(tot,las); q[++ttop]=Ques(l,i-m,tot,fr[x]); q[++ttop]=Ques(r+1,i-m,tot,las); las=tot; } }else { int x=read(),st=read(),ed=read(); q[++ttop]=Ques(x,++Q,fr[st],fr[ed]); } } sort(q+1,q+ttop+1); int last=1; for(int i=1;i<=n;i++) { while(q[last].pos==i&&last<=ttop) { if(q[last].typ<=0)cut(q[last].x),link(q[last].x,q[last].y); else ret[q[last].typ]=query(q[last].x,q[last].y); last++; } } for(int i=1;i<=Q;i++)printf("%d\n",ret[i]); return 0; }
浙公網安備 33010602011771號