題意：
一共n個(gè)位置，每個(gè)位置一個(gè)屬性k［i］，表示在i位置會被瞬間轉(zhuǎn)移到i+k［i］（然后又依次轉(zhuǎn)移）。問從一個(gè)點(diǎn)開始多少次會出界。并且支持修改k［i］。
題解：
把i向i+k［i］連邊，若i+k［i］出界就向外面的總根連邊。詢問就是求深度。
把一個(gè)節(jié)點(diǎn)splay到根之后（前提是根是原樹最開始的根），左邊一定是比它淺的（且一定是它到原樹根的一條鏈（因?yàn)閍ccess操作）），所以左兒子的size就是它的深度（根的深度為0）。
居然以前要寫一天的LCT半個(gè)小時(shí)就寫好了，要不是BZOJ的編譯器?？臻g不夠就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 = -48 + c ; isdigit （ c = getchar （ ） ） ; （ x *= 10 ） += c - 48 ） ;
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 ［2］， *fa ;
inline void update （ ） {
siz = ch ［0］ -》 siz + ch ［1］ -》 siz + 1 ;
}
} pool ［N 《《 1］， *root ［N］， *null ;
int n ;
inline void push_down （ node*& p ） {
if （ p -》 rev_flag ） {
swap （ p -》 ch ［0］， p -》 ch ［1］ ） ;
if （ p -》 ch ［0］ ！= null ） p -》 ch ［0］ -》 rev_flag ^= 1 ;
if （ p -》 ch ［1］ ！= null ） p -》 ch ［1］ -》 rev_flag ^= 1 ;
p -》 rev_flag = 0 ;
}
}
inline node* newnode （ node*& fa ） {
staTIc node* tp （ pool + 1 ） ;
tp -》 siz = 1 ; tp -》 rev_flag = 0 ;
return tp -》 fa = fa， tp -》 ch ［0］ = tp -》 ch ［1］ = 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 《《 1］ ;
inline void splay （ node* p ） {
if （ p == null ） return ;
// staTIc node* st ［N 《《 1］ ; staTIc int tp （ 0 ） ; RE?。。?！
int tp ;
st ［tp = 1］ = 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 ） ;
}
}
下載文檔
