比赛 |
清华集训2017模板练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
弹飞绵羊 |
最终得分 |
100 |
用户昵称 |
栋霸霸 |
运行时间 |
1.606 s |
代码语言 |
C++ |
内存使用 |
3.36 MiB |
提交时间 |
2017-07-17 14:50:46 |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=200010;
int a[maxn],bel[maxn],sum[maxn],to[maxn];
int n,m,K,Q;
int Query(int x){
int ret=0;
while(x!=-1){
ret+=sum[x];
x=to[x];
}
return ret;
}
int main(){
freopen("bzoj_2002.in","r",stdin);
freopen("bzoj_2002.out","w",stdout);
scanf("%d",&n);
m=sqrt(n+0.5);
for(int i=1;i<=n;i++){
if((i-1)%m==0)K++;
bel[i]=K;
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--){
if(i+a[i]>n){
to[i]=-1;
sum[i]=1;
}
else{
if(bel[i]==bel[i+a[i]]){
to[i]=to[i+a[i]];
sum[i]=sum[i+a[i]]+1;
}
else{
to[i]=i+a[i];
sum[i]=1;
}
}
}
scanf("%d",&Q);
while(Q--){
int op,x,y;
scanf("%d",&op);
if(op==1){
scanf("%d",&x);x++;
printf("%d\n",Query(x));
}
else{
scanf("%d%d",&x,&y);x++;
a[x]=y;
if(x+y>n){
sum[x]=1;
to[x]=-1;
}
else{
if(bel[x]==bel[x+y]){
to[x]=to[x+y];
sum[x]=sum[x+y]+1;
}
else{
to[x]=x+y;
sum[x]=1;
}
}
for(int p=x-1;bel[p]==bel[x];p--)
if(bel[p]==bel[p+a[p]])
sum[p]=sum[p+a[p]]+1,to[p]=to[p+a[p]];
}
}
return 0;
}