codeforces 13 E. Holes (分块)
http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来
n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]....
思路：分块大法好。具体见代码注释。以及。。。cin加速之后还是很慢。。。能不用就不用吧。
/* ***********************************************
Author :111qqz
Created Time :2016年02月20日 星期六 23时48分28秒
File Name :code/cf/problem/13E.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n,m;
8int cnt[N];//cnt[i]表示第i个洞的球跳出所在块所需要的步数
9int end[N]; //end[i]表示第i个洞的球跳出序列之前所经历的最后一个洞的序号
10int jmp[N]; //jmp[i]表示第i个洞的球跳出所在的块到下一个块的洞的序号。
11int a[N];
12int siz = 313; //sqrt(1E5)
13 int pos[N];
1void go ( int x)
2{
3 int ans = 0 ;
4 int e;
5 while (1)
6 {
7 if (x>n)
8 {
9 //cout<<e<<" "<<ans<<endl;
10 printf("%d %d\n",e,ans);
11 break;
12 }
13 ans +=cnt[x];
14 e = end[x];
15 x = jmp[x];
16 }
17 // cout<<"x:"<<x<<" cnt[x] :"<<cnt[x]<<endl;
1 // cout<<e<<" "<<ans<<endl;
2}
3void update( int i,int j)
4{
5 if (j>n)//跳出所有洞
6 {
7 cnt[i] = 1;
8 end[i] = i;
9 jmp[i] = n+1;//只要是一个大于n的数表示跳出就可以了
10 }
11 else
12 {
13 if (pos[i]==pos[j]) //在同一块
14 {
15 cnt[i]=cnt[j]+1;
16 end[i]=end[j];
17 jmp[i]=jmp[j];
18 }
19 else
20 {
21 cnt[i] = 1;
22 end[i]=end[j];
23 jmp[i] = j;
24 }
25 }
26}
27int main()
28{
29 #ifndef ONLINE_JUDGE
30 freopen("code/in.txt","r",stdin);
31 #endif
// ios::sync_with_stdio(false);
1 cin>>n>>m;
2 for ( int i = 1 ; i <= n ; i++)
3 {
4 scanf("%d",&a[i]);
5 pos[i] = (i-1)/siz;
6 }
7 for ( int i = n ; i >= 1 ; i--) update(i,i+a[i]);
1 while (m--)
2 {
3 int opt;
4 scanf("%d",&opt);
5 if (opt==0)
6 {
7 int x,y;
8 scanf("%d %d",&x,&y);
9 a[x]=y;
10 update(x,x+a[x]);
11 int pos = (x-1)/siz*siz;//pos表示x所在的块首下标
1 for ( int i = x-1 ; i >= pos; i--) update(i,i+a[i]);
2 }
3 else
4 {
5 int x;
6 scanf("%d",&x);
7 go(x);
8 }
9 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}