比赛 清华集训2017模板练习 评测结果 AAAAAAAAAA
题目名称 弹飞绵羊 最终得分 100
用户昵称 Cydiater 运行时间 1.603 s
代码语言 C++ 内存使用 4.13 MiB
提交时间 2017-07-17 17:25:10
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define FILE		"bzoj_2002"

const int MAXN=200005;
const int oo=0x3f3f3f3f;

int N,M,a[MAXN];

namespace LCT{
	struct tree{
		int son[2],siz,fa;
	}t[MAXN];
	int isrt(int k){
		if(!k)return 1;
		return k!=t[t[k].fa].son[1]&&k!=t[t[k].fa].son[0];
	}
	int get(int k){return k==t[t[k].fa].son[1];}
	void rel(int k){
		if(!k)return;
		int s0=t[k].son[0],s1=t[k].son[1];
		t[k].siz=1;
		if(s0)t[k].siz+=t[s0].siz;
		if(s1)t[k].siz+=t[s1].siz;
	}
	void rotate(int k){
		int fa=t[k].fa,ffa=t[fa].fa,w=get(k);
		if(!isrt(fa))t[ffa].son[fa==t[ffa].son[1]]=k;
		t[fa].son[w]=t[k].son[w^1];t[t[fa].son[w]].fa=fa;
		t[k].son[w^1]=fa;t[fa].fa=k;
		t[k].fa=ffa;
		rel(fa);rel(k);
	}
	void splay(int k){
		while(!isrt(k)){
			int fa=t[k].fa;
			if(!isrt(fa))rotate(get(k)==get(fa)?fa:k);
			rotate(k);
		}
	}
	void access(int k){
		int tmp=0;
		while(k){
			splay(k);
			t[k].son[1]=tmp;
			rel(k);
			tmp=k;
			k=t[k].fa;
		}
	}
	void Cut(int k){
		access(k);
		splay(k);
		int s0=t[k].son[0];
		t[s0].fa=t[k].son[0]=0;
		rel(k);
	}
	void Link(int x,int y){
		access(y);
		splay(y);
		access(x);
		splay(x);
		t[x].fa=y;
	}
}using namespace LCT;

namespace solution{
	void Prepare(){
		scanf("%d",&N);
		up(i,1,N){
			scanf("%d",&a[i]);
			t[i].fa=min(i+a[i],N+1);
			t[i].siz=1;
		}
		t[N+1].siz=1;
	}
	void Solve(){
		scanf("%d",&M);
		while(M--){
			int op;
			scanf("%d",&op);
			if(op==1){
				int x;
				scanf("%d",&x);
				x++;
				access(x);
				splay(x);
				printf("%d\n",t[x].siz-1);
			}else{
				int x,v;
				scanf("%d%d",&x,&v);
				x++;
				Cut(x);
				a[x]=v;
				Link(x,min(x+a[x],N+1));
			}
		}
	}
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}