正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P3203

---

題目大意

$n$個裝置。到第$i$個裝置會被往前彈$a_i$個。
兩種操作
修改$a_i$和詢問從$i$出發要多少次彈射可以彈出去。

---

解題思路

分塊。對于每個點，維護要多少步彈出該塊和彈出去后彈到哪里。
詢問就直接根據兩個數據，修改就直接重構整個塊。

時間復雜度:$O(n\sqrt{n})$

---

code

#include<cstdio> #include<cmath> #define N 200010 #define T 500 using namespace std; int n,m,x,t,a[N],L[T],R[T],step[N],to[N],pos[N]; void pre_work()//預處理 {for(int i=1;i<=t;i++)//塊邊界{L[i]=(i-1)*t+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--){if(j+a[j]<=R[i]) step[j]=step[j+a[j]]+1,to[j]=to[j+a[j]];else step[j]=1,to[j]=j+a[j];pos[j]=i;}//初始數據 } int ask(int x)//詢問 {int ans=0;while(x<=n)ans+=step[x],x=to[x];return ans; } void change(int i)//重構塊 {for(int j=R[i];j>=L[i];j--)if(j+a[j]<=R[i]) step[j]=step[j+a[j]]+1,to[j]=to[j+a[j]];else step[j]=1,to[j]=j+a[j]; } int main() {scanf("%d",&n);t=sqrt(n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);pre_work();scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d",&x);if(x==1){scanf("%d",&x);x++;printf("%d\n",ask(x));}else{scanf("%d",&x);x++;scanf("%d",&a[x]);change(pos[x]);}} }

總結

以上是生活随笔為你收集整理的P3203-[HNOI2010]弹飞绵羊【分块】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。