https://www.lydsy.com/JudgeOnline/problem.php?id=2002
分块（ √ ）
LCT（）
动态树（）
一、分块：
分块重要的是确定我们建立的数组要完成什么使命，这题是问从某点弹出序列需要几次，并要提供修改操作。既然分了块，那我们就要把操作缩小到块的范围，需要的是弹出整个序列的次数，我们就缩小到跳出这个块的次数；而最后query时就像并查集一样（？）一块一块地去找它的祖宗，所以再给它提供一个数组存这个点的落地位置。
tips：1）存次数和落地位置用结构体好像比两个独立的数组要快一些，但我不会分析o(￣┰￣*)ゞ
2）要用scanf，不然tle到崩溃
1 #include<bits/stdc++.h> 2 #define mem(a) memset(a,0,sizeof(a)) 3 #define ll long long 4 #define inf 0x3f3f3f3f 5 const int N=2e5+5; 6 const int M=1e3+10; 7 const ll lim=1e14+5; 8 using namespace std; 9 int mod=1e9+7; 10 int a[N],sum[N]; 11 int blo,l[N],r[N]; 12 int n,belong[N],k,num; 13 struct node{ 14 int cnt,tag; 15 }lazy[N]; 16 void build() 17 { 18 blo=sqrt(n); 19 num=n%blo>0?n/blo+1:n/blo; 20 for(int i=1;i<=num;i++) 21 { 22 l[i]=(i-1)*blo+1; 23 r[i]=i*blo; 24 } 25 r[num]=n; 26 for(int i=1;i<=n;i++) 27 belong[i]=(i-1)/blo+1; 28 for(int i=n;i>0;i--) 29 { 30 if(a[i]+i>n) 31 lazy[i].cnt=1; 32 else if(belong[i]==belong[a[i]+i]) 33 { 34 lazy[i].cnt=lazy[a[i]+i].cnt+1; 35 lazy[i].tag=lazy[a[i]+i].tag; 36 //因为i下一个会跳到a[i]+1位置，所以跳出块外的地方与后者一样 37 } 38 else 39 { 40 lazy[i].cnt=1; 41 lazy[i].tag=i+a[i]; 42 } 43 } 44 } 45 void add(int x,int c) 46 { 47 a[x]=c; 48 for(int i=x;i>=l[belong[x]];i--) 49 if(belong[i]==belong[i+a[i]]) 50 lazy[i].cnt=lazy[a[i]+i].cnt+1,lazy[i].tag=lazy[i+a[i]].tag; 51 else 52 lazy[i].cnt=1,lazy[i].tag=i+a[i]; 53 } 54 int query(int x) 55 { 56 int ans=0; 57 while(1) 58 { 59 ans+=lazy[x].cnt; 60 if(!lazy[x].tag) break; 61 x=lazy[x].tag; 62 } 63 return ans; 64 } 65 int main(){ 66 int m; 67 scanf("%d",&n); 68 for(int i=1;i<=n;i++) 69 scanf("%d",&a[i]); 70 scanf("%d",&m); 71 build(); 72 int i,j,k; 73 while(m--) 74 { 75 scanf("%d%d",&i,&j); 76 ++j; 77 if(i==1) 78 printf("%d ",query(j)); 79 if(i==2) 80 { 81 scanf("%d",&k); 82 add(j,k); 83 } 84 } 85 return 0; 86 }