比赛 |
清华集训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;
}