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