2002: [Hnoi2010]Bounce 彈飛綿羊(link-cut-tree)

2002: [Hnoi2010]Bounce 彈飛綿羊

題意：中文題就不解釋了。 解題思路：對於i，到i的綿羊會被彈到i+ki位置上，那麼我們連一條(i,i+ki)的邊，所有的關系建完之後，就是一個森林，而i位置被彈幾次，自然就是其深度了。這裡再做一個改進，設一個虛擬節點，將森林裡，樹的根都連在n+1這個節點上，那麼所有的關系就是一顆樹了。這樣做是方便操作。在修改這個操作的時候，我是先將a和a的父親斷開，也就是cut操作，然後將a和a的新父親連起來，而在這個過程中，會有換根的操作，所以，有了虛擬的根節點，那麼我們在query的時候，再將根換回n+1，那麼詢問就方便多了。 代碼：

#include
#include
#include
#define ls son[0][rt]
#define rs son[1][rt]
using namespace std ;
 
const int maxn = 211111 ;
int son[2][maxn] , fa[maxn] , is[maxn] , size[maxn] , rev[maxn] ;
 
void push_up ( int rt ) {
        size[rt] = size[ls] + size[rs] + 1 ;
}
 
void reverse ( int rt ) {
        if ( !rt ) return ;
        swap ( ls , rs ) ;
        rev[rt] ^= 1 ;
}
 
void push_down ( int rt ) {
        if ( rev[rt] ) {
                reverse ( ls ) ;
                reverse ( rs ) ;
                rev[rt] = 0 ;
        }
}
 
void down ( int rt ) {
        if ( !is[rt] ) down ( fa[rt] ) ;
        push_down ( rt ) ;
}
 
void rot ( int rt , int c ) {
        int y = fa[rt] , z = fa[y] ;
        son[!c][y] = son[c][rt] ; fa[son[c][rt]] = y ;
        son[c][rt] = y ; fa[y] = rt ;
        fa[rt] = z ;
        if ( is[y] ) is[y] = 0 , is[rt] = 1 ;
        else son[y==son[1][z]][z] = rt ;
        push_up ( y ) ;
}
 
void splay ( int rt ) {
        down ( rt ) ;
        while ( !is[rt] ) {
                int y = fa[rt] , z = fa[y] ;
                if ( is[y] ) rot ( rt , rt == son[0][y] ) ;
                else {
                        int c = ( rt == son[0][y] ) , d = ( y == son[0][z] ) ;
                        if ( c == d ) rot ( y , c ) , rot ( rt , c ) ;
                        else rot ( rt , c ) , rot ( rt , d ) ;
                }
        }
        push_up ( rt ) ;
}
 
void access ( int rt ) {
        for ( int v = 0 ; rt ; rt = fa[rt] ) {
                splay ( rt ) ;
                is[rs] = 1 ; is[v] = 0 ;
                rs = v ;
                v = rt ;
                push_up ( rt ) ;
        }
}
 
void change_root ( int rt ) {
        access ( rt ) ;
        splay ( rt ) ;
        reverse ( rt ) ;
}
 
int query ( int a , int b ) {
        while ( fa[a] ) a = fa[a] ;
        while ( fa[b] ) b = fa[b] ;
        return a == b ;
}
 
void cut ( int a , int b ) {
        if ( query ( a , b ) ) {
                change_root ( a ) ;
                access ( a ) ;
                splay ( b ) ;
                fa[b] = 0 ;
        }
}
 
void add ( int a , int b ) {
        if ( !query ( a , b ) ) {
                splay ( b ) ;
                fa[b] = a ;
        }
}
 
void init ( int rt ) {
        size[rt] = is[rt] = 1 ;
        son[0][rt] = son[1][rt] = fa[rt] = rev[rt] = 0 ;
}
 
int num[maxn] ;
int main () {
        int n , m , i , a , b , c ;
        while ( scanf ( "%d" , &n ) != EOF ) {
                for ( i = 1 ; i <= n + 1 ; i ++ ) init ( i ) ;
                for ( i = 1 ; i <= n ; i ++ ) {
                        scanf ( "%d" , &a ) ;
                        num[i] = a ;
                        if ( i + a <= n ) add ( i + a , i ) ;
                        else add ( n + 1 , i ) ;
                }
                scanf ( "%d" , &m ) ;
                while ( m -- ) {
                        scanf ( "%d%d" , &c , &a ) ;
                        a ++ ;
                        if ( c == 1 ) {
                                change_root ( n + 1 ) ;
                                access ( a ) ;
                                splay ( a ) ;
                                printf ( "%d\n" , size[son[0][a]] ) ;
                        }
                        else {
                                scanf ( "%d" , &b ) ;
                                int d = a + num[a] ; num[a] = b ;
                                cut ( a , min ( d , n + 1 ) ) ;
                                add ( min ( num[a] + a , n + 1 ) , a ) ;
                        }
                }
        }
        return 0 ;
}