BZOJ 2002 彈飛綿羊（分塊）
摘要：
題目：彈飛綿羊
這道題，據說是lct裸題，但是lct那麼高階的資料結構，我並不會，所以採取了學長講過的分塊做法，我們對序列分塊，可以定義兩個陣列，其中一個表示從當前位置跳出當前塊需要多少步，另一個數組表示從當前位置跳到下一塊會落在哪個位置，然後新修改就暴力修改當前塊，查詢就...
題目：ofollow,noindex">彈飛綿羊
這道題，據說是lct裸題，但是lct那麼高階的資料結構，我並不會，所以採取了學長講過的分塊做法，我們對序列分塊，可以定義兩個陣列，其中一個表示從當前位置跳出當前塊需要多少步，另一個數組表示從當前位置跳到下一塊會落在哪個位置，然後新修改就暴力修改當前塊，查詢就直接暴力跑塊外的結果。陣列初始化可以考慮倒著跑，然後分情況討論。這題被我們完美解決了。
下面上程式碼：
1 #include<iostream>
2 #include<cmath>
3 #include<cstring>
4 #include<algorithm>
5 #include<cstdio>
6 #define db double
7 using namespace std;
8 const int N=200005;
9 int n,m,a[N],t1,t2,t3,siz,s,t,to[N],stp[N];
10 int query(int p){
11int rt=0;while(~p){
12rt+=stp[p];p=to[p];
13} return rt;
14 } void update(int p,int da){
15s=p/siz*siz;t=(p/siz+1)*siz-1;
16a[p]=da;for(int i=p;i>=s;i--)
17if(i+a[i]>=n) to[i]=-1,stp[i]=1;
18else if(i+a[i]>t) to[i]=i+a[i],stp[i]=1;
19else to[i]=to[i+a[i]],stp[i]=stp[i+a[i]]+1;
20 } int main(){
21scanf("%d",&n);siz=(int)sqrt((db)n+0.5);
22for(int i=0;i<n;i++) scanf("%d",&a[i]);
23for(int i=n-1;~i;i--){
24t=(i/siz+1)*siz-1;
25if(i+a[i]>=n) to[i]=-1,stp[i]=1;
26else if(i+a[i]>t)
27to[i]=i+a[i],stp[i]=1;
28else to[i]=to[i+a[i]],
29stp[i]=stp[i+a[i]]+1;
30} scanf("%d",&m);
31while(m--){
32scanf("%d%d",&t1,&t2);
33if(t1==1) printf("%d\n",query(t2));
34else scanf("%d",&t3),update(t2,t3);
35} return 0;
36 }
分塊