大家都很強， 可與之共勉。
題意：
一共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=)