Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://www.lydsy.com/JudgeOnline/problem.php?id=2002
题意+思路： 同codeforces 13 E holes.
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}