/****************************************\
* Author : ztx
* Title  : [Hnoi2010]Bounce 弹飞绵羊
* ALG    : LCT
* CMT    :
* 对于i, 到i的绵羊会被弹到i+ki位置上, 那么我们连一条(i, i+ki)的边.
* 所有的关系建完之后, 就是一个森林, 而i位置被弹几次, 就是其深度.
* 这时设一个虚拟节点ROOT=n+1, 将森林里, 树的根都连在ROOT这个节点上,
* 那么所有的关系就是一颗树了.
* 在修改操作时, 先将u和u的父亲断开, 也就是cut操作,
* 再将u和u的新父亲连起来, 就是Link.
* 由于我们知道树的形态, 故可以免去换根操作
* Data   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [Hnoi2010]Bounce 弹飞绵羊
* ALG    : LCT
* CMT    :
* 对于i, 到i的绵羊会被弹到i+ki位置上, 那么我们连一条(i, i+ki)的边.
* 所有的关系建完之后, 就是一个森林, 而i位置被弹几次, 就是其深度.
* 这时设一个虚拟节点ROOT=n+1, 将森林里, 树的根都连在ROOT这个节点上,
* 那么所有的关系就是一颗树了.
* 在修改操作时, 先将u和u的父亲断开, 也就是cut操作,
* 再将u和u的新父亲连起来, 就是Link.
* 由于我们知道树的形态, 故可以免去换根操作
* Data   :
\****************************************/

#include <cstdio>

#define  maxn  200010LL
#define  null  0LL

int CH ;
void read(int& ret) {
     ret = 0 ; while (CH=getchar() , CH<'!') ;
     while (ret=ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int size[maxn] = {0} ;

#define left(u)    ch[u][0]
#define right(u)   ch[u][1]
#define min(a , b) (a)<(b)?(a):(b)

inline void Maintain(int u) {
	size[u] = size[left(u)]+size[right(u)]+1 ;
}

inline bool Isrt(int u) {
	return (!fa[u]) || ((left(fa[u])!=u)&&(right(fa[u])!=u)) ;
}

inline void zig(int x) {
    /* right rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
    Maintain(y) ;
}

inline void zag(int x) {
    /* left rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
    Maintain(y) ;
}

inline void Splay(int x) {
	int y , z ;
	while (!Isrt(x)) {
		y = fa[x] , z = fa[y] ;
		if (Isrt(y)) {
			if (left(y) == x) zig(x) ; else zag(x) ;
		} else {
			if (left(z) == y) {
				if (left(y) == x) zig(x) , zig(x) ;
				else zag(x) , zig(x) ;
			} else if (right(z) == y) {
				if (right(y) == x) zag(x) , zag(x) ;
				else zig(x) , zag(x) ;
			}
		}
	}
	Maintain(x) ;
}

inline void Access(int u) {
	for (int v = null ; u ; u = fa[u]) Splay(u) , right(u) = v , v = u , Maintain(u) ;
}

inline void Cut(int u , int v) {
    Access(u) , Splay(v) ; fa[v] = null ;
}

inline void Link(int u , int v) {
    Access(u) , Splay(u) ; right(u) = v , fa[v] = u ; Maintain(u) ;
}

inline int Query(int u) {
    Access(u) , Splay(u) ; return size[u]-1 ;
}

int n , m , i , j , k , cmd , ROOT , next , old_next ;
int K[maxn] ;

int main() {
	#define READ
	#ifdef  READ
		freopen("bzoj_2002.in" ,"r",stdin ) ;
		freopen("bzoj_2002.out","w",stdout) ;
	#endif
	read(n) ;
	for (i = 1 ; i <= n ; i ++ ) read(K[i]) ;
	ROOT = n+1 ;
	for (i = 1 ; i <= n+1 ; i ++ ) size[i] = 1 ;
	for (i = n ; i > 0 ; i -- ) {
        next = min(i+K[i] , ROOT) ; Link(next , i) ;
    }
    read(m) ;
	for (i = 1 ; i <= m ; i ++ ) {
		read(cmd) ;
		if (cmd == 1) {
            read(j) , j ++ ; printf("%d\n", Query(j) ) ;
		} else {
            read(j) , read(k) , j ++ ;
			old_next = min(K[j]+j , n+1) , next = min(k+j , n+1) ;
			Cut(old_next , j) , Link(next , j) ;
			K[j] = k ;
		}
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

• 相关文章
• 全局相关文章