[BZOJ2002][洛谷P3203][Hnoi2010]Bounce 弹飞绵羊（LCT维护链长）

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 16082 Solved: 8241
[Submit][Status][Discuss]

Description

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input

4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output

2
3

HINT

Source

Solution

　　我们按1-n编号哈，不用题目中的从0开始编号，因为0这个节点在蒟蒻写的LCT里面比较暧昧（雾），用它我会很方。。。

　　对于每个i如果k+k[i]<=n，那么视为存在边i->k+k[i]，否则视为存在边i->虚拟节点n+1。然后你会发现每个节点有且仅有一条出边，O，你想到了什么？内向树！然而节点n+1并没有出边所以这是一棵普通的树（不然怎么用LCT呢）。

　　然后对于查询x的答案就是x到n+1的链长，这个其实顺手就求出来了，只需要维护sz，然后split一下x和n+1，答案就是此时根的sz值减1。

　　至于修改操作，就是cut一下再link一下嘛。

　　还有就是，我再也不在BZOJ上随便用cout了，这常数也忒大了。。。

Code

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

inline int read(){

    int x=,w=;char ch=;

    while(!isdigit(ch)) w|=ch=='-',ch=getchar();

    while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();

    return w?-x:x;

}

int sz[N],f[N],c[N][];

bool rv[N];

#define lc c[x][0]

#define rc c[x][1]

inline bool nrt(int x){return c[f[x]][]==x||c[f[x]][]==x;}

inline void pushup(int x){sz[x]=sz[lc]+sz[rc]+;}

inline void rev(int x){lc^=rc^=lc^=rc;rv[x]^=;}

inline void pushdown(int x){if(rv[x]) rev(lc),rev(rc),rv[x]=;}

inline int get(int x){return c[f[x]][]==x;}

inline void link(int x,int y,int d){c[x][d]=y,f[y]=x;}

void rotate(int x){

    int y=f[x],z=f[y],d=get(x);

    if(nrt(y)) c[z][get(y)]=x;f[x]=z;

    link(y,c[x][d^],d);

    link(x,y,d^);

    pushup(y),pushup(x);

}

int st[N],tp;

void splay(int x){

    int t=x;

    st[tp=]=t;

    while(nrt(t)) st[++tp]=t=f[t];

    while(tp) pushdown(st[tp--]);

    for(;nrt(x);rotate(x))

        if(nrt(f[x])) get(x)^get(f[x])?rotate(x):rotate(f[x]);

}

void access(int x){

    for(int y=;x;x=f[y=x])

        splay(x),c[x][]=y,pushup(x);

}

void makert(int x){access(x),splay(x),rev(x);}

int findrt(int x){

    access(x),splay(x);

    while(lc) pushdown(x),x=lc;

    splay(x);return x;

}

void link(int x,int y){

    makert(x);if(findrt(y)^x) f[x]=y;

}

void cut(int x,int y){

    makert(x);

    if(findrt(y)==x&&f[y]==x&&!c[y][]) f[y]=c[x][]=,pushup(x);

}

void split(int x,int y){

    makert(x),access(y),splay(y);

}

int n,m,k[N];

#define to(x) min(x+k[x],n+1)

int main(){

    n=read();

    for(int i=;i<=n;++i) k[i]=read(),link(i,to(i));

    m=read();

    while(m--){

        int x=read(),y=read()+;

        if(x&){

            split(y,n+);

            printf("%d\n",sz[n+]-);

        }

        else{

            cut(y,to(y));

            k[y]=read();

            link(y,to(y));

        }

    }

    return ;

}

BZOJ2002