codeforces 13 E. Holes (分块)
http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来
n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]….
思路：分块大法好。具体见代码注释。以及。。。cin加速之后还是很慢。。。能不用就不用吧。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月20日 星期六 23时48分28秒
4File Name :code/cf/problem/13E.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=1E5+7;
34int n,m;
35int cnt[N];//cnt[i]表示第i个洞的球跳出所在块所需要的步数
36int end[N]; //end[i]表示第i个洞的球跳出序列之前所经历的最后一个洞的序号
37int jmp[N]; //jmp[i]表示第i个洞的球跳出所在的块到下一个块的洞的序号。
38int a[N];
39int siz = 313; //sqrt(1E5)
40 int pos[N];
41
42void go ( int x)
43{
44 int ans = 0 ;
45 int e;
46 while (1)
47 {
48 if (x>n)
49 {
50 //cout<<e<<" "<<ans<<endl;
51 printf("%d %d\n",e,ans);
52 break;
53 }
54 ans +=cnt[x];
55 e = end[x];
56 x = jmp[x];
57 }
58 // cout<<"x:"<<x<<" cnt[x] :"<<cnt[x]<<endl;
59
60 // cout<<e<<" "<<ans<<endl;
61}
62void update( int i,int j)
63{
64 if (j>n)//跳出所有洞
65 {
66 cnt[i] = 1;
67 end[i] = i;
68 jmp[i] = n+1;//只要是一个大于n的数表示跳出就可以了
69 }
70 else
71 {
72 if (pos[i]==pos[j]) //在同一块
73 {
74 cnt[i]=cnt[j]+1;
75 end[i]=end[j];
76 jmp[i]=jmp[j];
77 }
78 else
79 {
80 cnt[i] = 1;
81 end[i]=end[j];
82 jmp[i] = j;
83 }
84 }
85}
86int main()
87{
88 #ifndef ONLINE_JUDGE
89 freopen("code/in.txt","r",stdin);
90 #endif
91
92// ios::sync_with_stdio(false);
93
94 cin>>n>>m;
95 for ( int i = 1 ; i <= n ; i++)
96 {
97 scanf("%d",&a[i]);
98 pos[i] = (i-1)/siz;
99 }
100 for ( int i = n ; i >= 1 ; i--) update(i,i+a[i]);
101
102 while (m--)
103 {
104 int opt;
105 scanf("%d",&opt);
106 if (opt==0)
107 {
108 int x,y;
109 scanf("%d %d",&x,&y);
110 a[x]=y;
111 update(x,x+a[x]);
112 int pos = (x-1)/siz*siz;//pos表示x所在的块首下标
113
114 for ( int i = x-1 ; i >= pos; i--) update(i,i+a[i]);
115 }
116 else
117 {
118 int x;
119 scanf("%d",&x);
120 go(x);
121 }
122 }
123
124
125
126 #ifndef ONLINE_JUDGE
127 fclose(stdin);
128 #endif
129 return 0;
130}