题目传送门
题意分析
其实用 LCT 可以很好维护，但是我们并不会 LCT。
因此考虑一些其他的数据结构来维护。发现并没有什么特别适合的数据结构，考虑分块。
记 \(\textit{step}_i\) 表示 \(i\) 跳出块的步数，\(\textit{to}_i\) 表示跳出到了哪里。
按照 \(\sqrt n\) 为块长分块。记 \(\operatorname{pos}(i),\operatorname{edgeL}(x),\operatorname{edgeR}(x)\) 分别表示 \(i\) 所在块编号，块 \(x\) 的左边界，块 \(x\) 的右边界。
预处理的时候，有：
- 若 \(i+k_i\leq\operatorname{edgeR}(\operatorname{pos}(i))\)，则有 \(\textit{step}_i=\textit{step}_{i+k_i}+1,\textit{to}_i=\textit{to}_{i+k_i}\)。
- 否则有 \(\textit{step}_i=1,\textit{to}_i=i+k_i\)。
更新的时候块内同理重构即可。
时间复杂度： \(\mathcal O\left((n+m)\sqrt n\right)\)。
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e5;
int n,size,k[N+1];
int pos(int x){return (x+size-1)/size;
}
int edgeL(int x){return (x-1)*size+1;
}
int edgeR(int x){return min(x*size,n);
}
int step[N+1],to[N+1];
void pre(){size=sqrt(n);for(int i=n;1<=i;i--){if(i+k[i]<=edgeR(pos(i))){step[i]=step[i+k[i]]+1;to[i]=to[i+k[i]];}else{step[i]=1;to[i]=i+k[i];}}
}
int query(int x){int ans=0;while(x<=n){ans+=step[x];x=to[x];}return ans;
}
void change(int x,int v){k[x]=v;for(int id=pos(x),i=edgeR(id);edgeL(id)<=i;i--){int x=i;step[i]=0;if(i+k[i]>edgeR(id)){to[i]=i+k[i];step[i]=1;}else{to[i]=to[i+k[i]];step[i]=step[i+k[i]]+1;}}
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>k[i];}pre();int m;cin>>m;while(m--){int op,i,j;cin>>op>>i;i++;if(op==1){cout<<query(i)<<'\n';}else{cin>>j;change(i,j);}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}