大家都很强， 可与之共勉。
题意：
一共n个位置，每个位置一个属性k[i]，表示在i位置会被瞬间转移到i+k[i]（然后又依次转移）。问从一个点开始多少次会出界。并且支持修改k[i]。
题解：
把i向i+k[i]连边，若i+k[i]出界就向外面的总根连边。询问就是求深度。
把一个节点splay到根之后（前提是根是原树最开始的根），左边一定是比它浅的（且一定是它到原树根的一条链（因为access操作）），所以左儿子的size就是它的深度（根的深度为0）。
居然以前要写一天的LCT半个小时就写好了，要不是BZOJ的编译器栈空间不够就1A了
/**************************************************************
Problem: 2002
User: Lazer2001
Language: C++
Result: Accepted
Time:1988 ms
Memory:22324 kb
****************************************************************/
# include <bits/stdc++.h>
inline int read ( ) {
register int x, c ;
while ( isspace ( c = getchar ( ) ) ) ;
for ( x = - + c ; isdigit ( c = getchar ( ) ) ; ( x *= ) += c - ) ;
return x ;
}
template < class T > inline T min ( const T& a, const T& b ) { return a < b ? a : b ; }
template < class T > inline void swap ( T& a, T& b ) { T c ( a ) ; a = b, b = c ; }
# define N 200010
class LinkCutTree {
private :
struct node {
int siz ;
bool rev_flag ;
node *ch [], *fa ;
inline void update ( ) {
siz = ch [] -> siz + ch [] -> siz + ;
}
} pool [N << ], *root [N], *null ;
int n ;
inline void push_down ( node*& p ) {
if ( p -> rev_flag ) {
swap ( p -> ch [], p -> ch [] ) ;
if ( p -> ch [] != null ) p -> ch [] -> rev_flag ^= ;
if ( p -> ch [] != null ) p -> ch [] -> rev_flag ^= ;
p -> rev_flag = ;
}
}
inline node* newnode ( node*& fa ) {
static node* tp ( pool + ) ;
tp -> siz = ; tp -> rev_flag = ;
return tp -> fa = fa, tp -> ch [] = tp -> ch [] = null, tp ++ ;
}
# define isroot( p ) ( p -> fa == null || ( p -> fa -> ch [0] != p && p -> fa -> ch [1] != p ) )
# define isrs( p ) ( p == p -> fa -> ch [1] )
inline void rotate ( node* p ) {
if ( p == null || isroot ( p ) ) return ;
bool d ( isrs ( p ) ) ;
node* par = p -> fa ;
par -> ch [d] = p -> ch [! d] ;
if ( p -> ch [! d] != null ) p -> ch [! d] -> fa = par ;
if ( ! isroot ( par ) ) par -> fa -> ch [isrs ( par )] = p ; // !isroot(par)
p -> fa = par -> fa ;
par -> fa = p ;
p -> ch [! d] = par ;
par -> update ( ) ; p -> update ( ) ;
}
node* st [N << ] ;
inline void splay ( node* p ) {
if ( p == null ) return ;
// static node* st [N << 1] ; static int tp ( 0 ) ; RE!!!!
int tp ;
st [tp = ] = p ;
for ( node* t = p ; ! isroot ( t ) ; t = t -> fa ) st [++ tp] = t -> fa ;
while ( tp ) push_down ( st [tp --] ) ;
while ( ! isroot ( p ) ) {
if ( isrs ( p ) == isrs ( p -> fa ) && ! isroot ( p -> fa ) ) rotate ( p -> fa ) ;
rotate ( p ) ;
}
}
# undef isrs
# undef isroot
inline void access ( node* p ) {
for ( node* pre = null ; p != null ; pre = p, p = p -> fa )
splay ( p ), p -> ch [] = pre, p -> update ( ) ;
}
inline void makeroot ( node* p ) {
access ( p ) ; splay ( p ) ; p -> rev_flag ^= ;
}
inline void cut ( node* p, node* q ) {
makeroot ( p ) ; access ( q ) ; splay ( q ) ;
q -> ch [] = null, p -> fa = null ;
q -> update ( ) ;
}
inline void link ( node* p, node* q ) {
makeroot ( p ) ; p -> fa = q ;
}
inline int dep ( node* p ) {
makeroot ( root [n + ] ) ;
access ( p ) ;
splay ( p ) ;
return p -> ch [] -> siz ;
}
public :
LinkCutTree ( ) {
null = pool ;
null -> siz = ; null -> rev_flag = ;
null -> ch [] = null -> ch [] = null -> fa = null ;
}
LinkCutTree ( int n ) : n ( n ) {
null = pool ;
null -> siz = ; null -> rev_flag = ;
null -> ch [] = null -> ch [] = null -> fa = null ;
for ( register int i = ; i <= n + ; ++ i ) root [i] = newnode ( null ) ;
}
inline void access ( int u ) { access ( root [u] ) ; }
inline void makeroot ( int u ) { makeroot ( root [u] ) ; }
inline void cut ( int u, int v ) { cut ( root [u], root [v] ) ; }
inline void link ( int u, int v ) { link ( root [u], root [v] ) ; }
inline int dep ( int u ) { return dep ( root [u] ) ; }
} T ;
int a [N] ;
# undef N
//# define ZJC_LOCAL
int main ( ) {
# ifdef ZJC_LOCAL
freopen ( "in.txt", "r", stdin ) ;
freopen ( "out.txt", "w", stdout ) ;
# endif
int n ( read ( ) ) ;
T = LinkCutTree ( n ) ;
for ( int i = ; i <= n ; ++ i ) {
T.link ( i, min ( i + ( a [i] = read ( ) ), n + ) ) ;
}
for ( int m = read ( ) ; m ; -- m ) {
int opt ( read ( ) ) ;
if ( opt == ) {
int u ( read ( ) + ) ; // + 1 !!!
printf ( "%d\n", T.dep ( u ) ) ;
} else {
int u ( read ( ) + ), k ( read ( ) ) ;
T.cut ( u, min ( u + a [u], n + ) ) ;
T.link ( u, min ( u + ( a [u] = k ), n + ) ) ;
}
}
}
数据生成器（随机）
# include <bits/stdc++.h>
inline int rd ( ) {
return rand ( ) << | rand ( ) ;
}
int main ( ) {
srand ( time ( ) ) ;
freopen ( "in.txt", "w", stdout ) ;
int n = , m = ;
printf ( "%d\n", n ) ;
for ( int i = ; i <= n ; ++ i ) printf ( "%d ", rd ( ) % + ) ;
printf ( "\n%d\n", m ) ;
while ( m -- ) {
int opt ( rand ( ) % + ) ;
printf ( "%d ", opt ) ;
if ( opt == ) {
printf ( "%d\n", rd ( ) % n ) ;
} else {
printf ( "%d %d\n", rd ( ) % n, rd ( ) % + ) ;
}
}
}
震惊！！！分块比LCT跑得快！！！
这莫非是根号算法的胜利？（滑稽）
短且好些好调，1A.
处理出每个点跳出那个块的步数，然后再处理出每个点跳出块到下一个地点是什么地方（可转移）。
倒着处理。
每次修改只会对块内产生影响（很好想）。
于是就很简单了。
复杂度O（(n+m)sqrt（n））
比log快，LCT自带大常数……
/**************************************************************
Problem:
User: Lazer2001
Language: C++
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
# include <bits/stdc++.h>
inline int read ( ) {
register int x, c ;
while ( isspace ( c = getchar ( ) ) ) ;
for ( x = - + c ; isdigit ( c = getchar ( ) ) ; ( x *= ) += c - ) ;
return x ;
}
template < class T > inline T min ( const T& a, const T& b ) { return a < b ? a : b ; }
# define N 200020
int k [N], step [N], nxt [N], pos [N] ;
# undef N
int n ;
inline void solve ( int i ) {
int pro = min ( i + k [i], n + ) ;
if ( pos [i] == pos [pro] ) {
step [i] = step [pro] + ;
nxt [i] = nxt [pro] ;
} else {
step [i] = ;
nxt [i] = pro ;
}
}
//# define ZJC_LOCAL
int main ( ) {
# ifdef ZJC_LOCAL
freopen ( "in.txt", "r", stdin ) ;
freopen ( "out.txt", "w", stdout ) ;
# endif
n = read ( ) ;
for ( int i = ; i <= n ; ++ i ) k [i] = read ( ) ;
int blk = ( int ) sqrt ( n + ) ;
for ( int i = ; i <= n ; ++ i ) pos [i] = ( i - ) / blk + ;
pos [n + ] = pos [n] + ; // !!!convenient;
for ( int i = n ; i >= ; -- i ) solve ( i ) ;
for ( int ocnt = read ( ) ; ocnt ; -- ocnt ) {
int opt ( read ( ) ) ;
if ( opt == ) {
int ans ( ) ;
for ( int i = read ( ) + ; i != n + ; i = nxt [i] ) ans += step [i] ; // pos + !!!
printf ( "%d\n", ans ) ;
} else {
int p ( read ( ) + ) ; // pos + !!!
k [p] = read ( ) ;
for ( int i = p ; i >= ; -- i ) {
if ( pos [i] != pos [p] ) break ;
solve ( i ) ;
}
}
}
}
![BZOJ 2002：Bounce 弹飞绵羊（分块）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)