弹飞绵羊

单点修改 + 单点查询

#include <cstdio>
#include <cmath>
using namespace std;

const int N=200100;
int n,Q,T,x,y,L[N],R[N],a[N],w[N],s[N],pos[N];

int ask(int x)
{
  int sum=0;
  while (x<=n)                        //没有被弹飞
  {
    sum+=s[x];                        //次数：累计跳出区间的标记
    x=w[x];                           //跳到下一个区间的第一个弹力装置
  }
  return sum;
}

void change(int x,int y)
{
  a[x]=y;
  for (int i=x;i>=L[pos[x]];i--)                       //暴力修改
    if (i+a[i]>R[pos[x]]) s[i]=1,w[i]=i+a[i];          //注释48+49行
    else s[i]=s[i+a[i]]+1,w[i]=w[i+a[i]];
}

int main()
{
  scanf("%d",&n);                    //序列长度
  for (int i=1;i<=n;i++)             //读取序列
    scanf("%d",&a[i]);
  T=sqrt(n);                         //块大小
  for (int i=1;i<=T;i++)
  {
    L[i]=R[i-1]+1;                   //块的左端点
    R[i]=i*T;                        //块的右端点
  }
  if (R[T]<n)                        //如果存在最后一块
  {
    T++;
    L[T]=R[T-1]+1;
    R[T]=n;
  }
  for (int i=1;i<=T;i++)
    for (int j=R[i];j>=L[i];j--)    //倒序更新s[]w[]两个标记
    {
      pos[j]=i;                     //标记块
      if (j+a[j]>R[i]) s[j]=1,w[j]=j+a[j];             //如果弹力系数加上弹力装置的位置超出这个块的区间，s[j]标记1次就能跳出。w[j]标记弹到哪个弹力装置
      else s[j]=s[j+a[j]]+1,w[j]=w[j+a[j]];            //如果弹力系数加上弹力装置的位置没有超出这个块的区间，s[j]标记跳到的下一个弹力装置+1，w[j]也标记跳到的下一个弹力装置的跳出区间后的第一个弹力装置
    }
  scanf("%d",&Q);                  //操作次数
  while (Q--)
  {
    scanf("%d",&x);
    if (x==1)                      //查询
    {
      scanf("%d",&x);
      printf("%d\n",ask(x+1));
    }
    else                          //修改
    {
      scanf("%d%d",&x,&y);
      change(x+1,y);
    }
  }
  return 0;
}

笔记：维护好s[]和w[]两个标记，一个标记弹出这个区间需要几次，一个记录弹出块区间后第一个落到其它块的下标位置。查询就是累加s[]，修改也是修改原序列a[]和更新s[]和w[]