【洛谷P3203】弹飞绵羊【分块】

本文主要是介绍【洛谷P3203】弹飞绵羊【分块】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P3203
有 $n$ 个装置，每个装置会把羊往后弹 $a [i]$ ，要求支持一下操作：

$1\ x$ ，求从第 $x$ 个弹射装置开始需要弹多少次才能把羊弹走。
$2\ x\ y$ ，将第 $x$ 个弹射装置的 $a [i]$ 改为 $y$ 。

思路：

这道题不说是分块基本就没思路了。
但是一知道是分块就很好解了。
我们分成 $\sqrt n$ 个块，每一个弹射装置维护两个值：

$w [i]$ ，弹出这个块之后回到哪一个弹射装置。
$s [i]$ ，要多少次才能弹出这个块。

那么对于每一个操作:

如果是 $1$ 操作，那么就从点 $x$ 开始，相当于会弹 $s [x]$ 次到 $w [x]$ ，那么再把 $w [x]$ 当作 $x$ 来继续求。
每个块最多经过一次，有 $\sqrt n$ 个块，所以时间复杂度为 $O(\sqrt n)$
如果是 $2$ 操作，那么就把这个块暴力重新初始化一遍。这个块最多有 $\sqrt n$ 个元素，时间复杂度 $O(\sqrt n)$

总时间复杂度为 $O(Q\sqrt n)$ 。其中 $Q$ 为询问个数。

代码：

#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];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--){pos[j]=i;if (j+a[j]>R[i]) s[j]=1,w[j]=j+a[j];else s[j]=s[j+a[j]]+1,w[j]=w[j+a[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;
}