本地能400ms 上了洛谷就超时

#include<bits/stdc++.h>
using namespace std;
const int MaxN=200000,MaxM=100000;//,Mod=51061;
struct Edge{
	Edge(){}
	Edge(int to,int next)
		:to(to),next(next){}
	int to,next;
}edge[MaxN*2+1];
int cnt=0,h[MaxN+1];
void AddEdge(int from,int to){
	edge[++cnt]=Edge(to,h[from]);
	h[from]=cnt;
}
int n,m;
struct Node{
	Node(){}
	int rev;
	int size;
	int prt,lc,rc;
}tree[MaxN+1];
bool IsRoot(int u){
	if((!tree[u].prt)||(tree[tree[u].prt].lc!=u&&tree[tree[u].prt].rc!=u))
		return true;
	else
		return false;
}
void PushUp(int u){tree[u].size=tree[tree[u].lc].size+tree[tree[u].rc].size+1;}
void PushDown(int u){
	if(tree[u].rev){
		swap(tree[u].lc,tree[u].rc);
		tree[tree[u].lc].rev^=1;
		tree[tree[u].rc].rev^=1;
		tree[u].rev=0;
	}
}
void Zag(int y){
	int x=tree[y].prt;
	int prt=tree[x].prt;
	int mid=tree[y].lc;
	tree[mid].prt=x;
	tree[x].rc=mid;
	tree[x].prt=y;
	tree[y].lc=x;
	tree[y].prt=prt;
	if(tree[prt].lc==x||tree[prt].rc==x){
		if(x==tree[prt].lc)tree[prt].lc=y;
		else tree[prt].rc=y;
	}
	PushUp(x);
	PushUp(y);
}
void Zig(int x){
	int y=tree[x].prt;
	int prt=tree[y].prt;
	int mid=tree[x].rc;
	tree[mid].prt=y;
	tree[y].lc=mid;
	tree[y].prt=x;
	tree[x].rc=y;
	tree[x].prt=prt;
	if(tree[prt].lc==y||tree[prt].rc==y){
		if(y==tree[prt].lc)tree[prt].lc=x;
		else tree[prt].rc=x;
	}
	PushUp(y);
	PushUp(x);
}
void Rotate(int u){
	if(tree[tree[u].prt].rc==u)Zag(u);
	else Zig(u);
}
int s[MaxN+1];
void Splay(int u){
	int top=0;
	int now=u;
	while(true){
		s[++top]=now;
		if(IsRoot(now))break;
		now=tree[now].prt;
	}
	for(;top;top--)PushDown(s[top]);
	while(!IsRoot(u)){
		if(IsRoot(tree[u].prt)){Rotate(u);}
		else{
			if(
				(u==tree[tree[u].prt].lc&&tree[u].prt==tree[tree[tree[u].prt].prt].lc)||
				(u==tree[tree[u].prt].rc&&tree[u].prt==tree[tree[tree[u].prt].prt].rc)
			)
			{Rotate(tree[u].prt);Rotate(u);}else{Rotate(u);Rotate(u);}
		}
	}
	PushUp(u);
}
void Access(int u){
	for(int x=0;u;x=u,u=tree[u].prt){
		Splay(u);
		tree[u].rc=x;
		PushUp(u);
	}
}
void BeRoot(int u){
	Access(u);Splay(u);
	tree[u].rev^=1;
}
int FindRoot(int u){
	Access(u);Splay(u);
	for(;tree[u].lc;u=tree[u].lc)PushDown(u);
	Splay(u);
	return u;
}
void BeClose(int u,int v){
	BeRoot(u);
	Access(v);Splay(u);
}
void Link(int u,int v){
	BeRoot(u);
//	if(FindRoot(v)==u)return;
	tree[u].prt=v;
}
void Cut(int u,int v){
//	BeRoot(u);
//	if(FindRoot(v)==u&&tree[v].prt==u&&(!tree[v].lc)){
//		tree[v].prt=0;
//		tree[u].rc=0;
//		PushUp(u);
//	}
	BeRoot(v);
	Access(u);Splay(u);
	tree[v].prt=0;
	tree[u].lc=0;
	PushUp(u);
}
int a[MaxN+1];
void Read(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i+a[i]>n)Link(n+1,i);
		else Link(i+a[i],i);
	}
}
void Solve(){
	cin>>m;
	for(int i=1;i<=m;i++){
		char s;int u,v;
		cin>>s;
		if(s=='1'){
			cin>>u;
			u++;
			BeClose(n+1,u);
			cout<<tree[n+1].size-1<<'\n';
		}else if(s=='2'){
			cin>>u>>v;
			u++;
			if(u+a[u]>n)Cut(n+1,u);
			else Cut(u+a[u],u);
			if(u+v>n)Link(n+1,u);
			else Link(u+v,u);
			a[u]=v;
		}
//		cout<<"--------\n";
//		for(int i=1;i<=n+1;i++)cout<<tree[i].size<<' '<<tree[i].prt<<' '<<tree[i].lc<<' '<<tree[i].rc<<'\n';
//		cout<<"--------\n";
	}
}
int main(){
//	freopen("P3203_10.in","r",stdin);
//	freopen("P3203_10.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	Read();
	Solve();
	return 0;
}