Bounce弹飞绵羊 bzoj-2002 Hnoi-2010
题目大意：n个格子，每一个格子有一个弹簧，第i个格子会将经过的绵羊往后弹k[i]个，达到i+k[i]。如果i+k[i]不存在，就表示这只绵羊被弹飞了。m次操作，支持：单点修改。查询：将一只绵羊放在一个格子上问弹几次能弹飞。
注释：$1\le n \le 2\cdot 10^5$，$1\le m \le 10^5$。
想法：当场切，先容我得瑟一会儿(～￣▽￣)～
说这个题，我们将i于i+k[i]连边，如果i+a[i]超过了n，就弄一个超级点Super_Point，把所有能弹飞的格子都连向超级点。然后我们发现，修改操作就是加边删边，查询操所就是从Super_Point到单点之间的路径点数，这个过程我们可以用LCT维护。
最后，附上丑陋的代码... ...
#include#include #include #include #define ls ch[p][0]#define rs ch[p][1]#define get(x) (ch[f[x]][1]==x)#define N 200010 using namespace std;int ch[N][2],f[N],size[N],a[N];bool rev[N]={false};inline bool isroot(int p){ return ch[f[p]][0]!=p&&ch[f[p]][1]!=p;}inline void pushup(int p){ if(!p) return; size[p]=1; if(ls) size[p]+=size[ls]; if(rs) size[p]+=size[rs];}inline void pushdown(int p){ if(!rev[p]) return; swap(ch[ls][0],ch[ls][1]),swap(ch[rs][0],ch[rs][1]); rev[ls]^=1; rev[rs]^=1; rev[p]=0;}void update(int p){ if(!isroot(p)) update(f[p]); pushdown(p);}void rotate(int x){ int y=f[x],z=f[y],k=get(x); if(!isroot(y)) ch[z][ch[z][1]==y]=x; ch[y][k]=ch[x][!k]; f[ch[y][k]]=y; ch[x][!k]=y; f[y]=x; f[x]=z; pushup(y); pushup(x);}void splay(int x){ update(x); for(int t;t=f[x],!isroot(x);rotate(x)) { if(!isroot(t)) rotate(get(x)==get(t)?t:x); }}void access(int p){ for(int t=0;p;t=p,p=f[p]) { splay(p); rs=t; pushup(p); }}void makeroot(int p){ access(p);splay(p); swap(ls,rs);rev[p]^=1;}inline void link(int x,int p){ makeroot(x); splay(p); f[x]=p;}inline void cut(int x,int p){ makeroot(x); access(p); splay(p); ls=f[x]=0;}int main(){ int n; cin >> n ; int sp=n+1; for(int i=1;i<=sp;i++) size[i]=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); link(i,min(a[i]+i,sp)); } int m,x,y,opt; cin >> m ; for(int i=1;i<=m;i++) { scanf("%d%d",&opt,&x); x++; if(opt==1) { makeroot(sp); access(x); splay(x); printf("%d\n",size[ch[x][0]]); } else { scanf("%d",&y); cut(x,min(x+a[x],sp)); a[x]=y; link(x,min(x+a[x],sp)); } } return 0;}
小结：又是一道LCT裸题... ...