bzoj2002: [Hnoi2010]Bounce 弹飞绵羊 (分块)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年02月21日 星期日 02时29分39秒
  4File Name :code/bzoj/2002.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=2E5+7;
 34int n,m;
 35int siz = 450; //sqrt(2E5)
 36int a[N];
 37int pos[N];
 38int cnt[N];
 39int nxt[N];
 40int end[N];
 41
 42
 43void go( int x)
 44{
 45    int ans = 0  ;
 46    while (1)
 47    {
 48	if (x>=n)
 49	{
 50	    printf("%d\n",ans);
 51	    break;
 52	}
 53	ans +=cnt[x];
 54	x = nxt[x];
 55//	cout<<"nxt[x]:"<<nxt[x]<<endl;
 56    }
 57}
 58void update ( int i,int j)
 59{
 60    if (j>=n)
 61    {
 62	cnt[i]=1;
 63	nxt[i]=n;
 64	end[i]=i;
 65    }
 66    else
 67    {
 68	if (pos[i]==pos[j])
 69	{
 70	    cnt[i] = cnt[j] + 1;
 71	    nxt[i] = nxt[j];
 72	    end[i]=end[j];
 73	}
 74	else
 75	{
 76	    cnt[i] = 1;
 77	    nxt[i] = j;
 78	    end[i] = end[j];
 79	}
 80    }
 81}
 82int main()
 83{
 84	#ifndef  ONLINE_JUDGE 
 85	freopen("code/in.txt","r",stdin);
 86  #endif
 87
 88	scanf("%d",&n);
 89	for ( int i = 0 ; i < n ;i++)
 90	{
 91	    scanf("%d",&a[i]);
 92	    pos[i] = i/siz;
 93	}
 94
 95	for ( int i = n - 1 ; i >= 0 ; i--) update(i,i+a[i]);
 96
 97	scanf("%d",&m);
 98	while (m--)
 99	{
100	    int opt;
101	    scanf("%d",&opt);
102	    if (opt==1)
103	    {
104		int x;
105		scanf("%d",&x);
106		go(x);
107	    }
108	    else
109	    {
110		int x,y;
111		scanf("%d %d",&x,&y);
112		a[x]=y;
113		update(x,x+a[x]);
114		int p = pos[x]*siz;
115		for ( int i = x-1  ; i >= p ; i--) update(i,i+a[i]);
116	    }
117	}
118
119  #ifndef ONLINE_JUDGE  
120  fclose(stdin);
121  #endif
122    return 0;
123}