弹飞绵羊-LCT

题目描述

题解

新建一个点$n+1$，如果从该点被弹飞就连边到$n+1$，其他操作都为LCT基本操作
询问时，只需$makeroot(j),access(n+1),splay(n+1)$,答案即为$size[n+1]-1$;

代码实现

#include//P2147
#define M 1000009
using namespace std;
int read(){char ch;int f=1,re=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar())if(ch=='-'){f=-1,ch=getchar();}for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';return re*f; 
}
int c[M][2],pa[M],n,m,q[M],a[M],size[M];
bool rev[M];
inline bool root(int x){int k=pa[x];return c[k][0]!=x&&c[k][1]!=x; 
}
void upt(int x) {size[x] = 1;if (c[x][1]) size[x]+=size[c[x][1]];if (c[x][0]) size[x]+=size[c[x][0]];
}
void pushdown(int x){if(rev[x]){rev[c[x][0]]^=1,rev[c[x][1]]^=1;swap(c[x][0],c[x][1]);rev[x]^=1;}
}
void rorate(int k){int fa=pa[k],gfa=pa[fa];int l=c[fa][1]==k, r=l^1;if(!root(fa))c[gfa][c[gfa][1]==fa]=k;pa[k]=gfa,pa[c[k][r]]=fa,pa[fa]=k;c[fa][l]=c[k][r];c[k][r]=fa; upt(k),upt(fa);
}
void splay(int k){int top=0;q[++top]=k;for(int x=k;!root(x);x=pa[x]) q[++top]=pa[x];while(top) pushdown(q[top--]);while(!root(k)){int fa=pa[k],gfa=pa[fa];if(!root(fa)){if(c[fa][0]==k^c[gfa][0]==fa) rorate(k);else rorate(fa);}rorate(k);}upt(k);
}
void access(int x){for(int i=0;x;i=x,x=pa[x]){splay(x),c[x][1]=i;if(i) pa[i]=x,upt(x);}
}
void makeroot(int x){access(x),splay(x),rev[x]^=1;
}
void link(int x,int y){makeroot(x),pa[x]=y,splay(x);
}
void cut(int x,int y){makeroot(x),access(y),splay(y),c[y][0]=pa[x]=0,upt(y);
}
int getans(int x){makeroot(x),access(n+1),splay(n+1);return size[n+1]-1;
}
int main(){char s[20];int x,y;n=read();for(int i=1;i<=n+1;i++) size[i]=1; for(int i=1;i<=n;i++){a[i]=read();link(i,min(i+a[i],n+1));}m=read();for(int i=1;i<=m;i++){int type=read();if(type==1){x=read()+1;printf("%d\n",getans(x));}if(type==2){x=read()+1,y=read();cut(x,min(a[x]+x,n+1));link(x,min(y+x,n+1));a[x]=y;}}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！