CodeForces 13E 分块-白红宇

CodeForces 13E 分块

阅读量：5842 次

发布时间：2019-06-18

本文共 2150 字，大约阅读时间需要 7 分钟。

题目链接：http://codeforces.com/problemset/problem/13/E

题意：给定n个弹簧和每个弹簧初始的弹力a[]。当球落在第i个位置。则球会被弹到i+a[i]的位置.

现在有2种操作：

1 a b:把第a个弹簧的弹力修改为b。

2 a:当球初始放入的位置为a时，需要弹几次才会弹出n。弹出前的最后一个位置是多少。输出位置和次数。

思路：和一样。然后记录一个最后弹出去的位置preidx。每次弹出当前块的时候记录当前的位置即可。然后最后再暴力模拟最后弹出去时所在的块的位置即可。

#define _CRT_SECURE_NO_DEPRECATE#include
     
        #include
      
         #include
       
        #include
        
           #include
         
            #include
          
            #include
           
            #include
            
             #include
             
              #include
              using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, q;int a[MAXN], cnt[MAXN], to[MAXN];void build(){ block = (int)sqrt(n + 0.5); num = n / block; if (n%block){ num++; } for (int i = 1; i <= num; i++){ L[i] = (i - 1)*block + 1; R[i] = i*block; } R[num] = n; for (int i = 1; i <= n; i++){ belong[i] = ((i - 1) / block) + 1; } for (int i = num; i>=1; i--){ for (int j = R[i]; j >= L[i]; j--){ if (j + a[j]>R[i]){ cnt[j] = 1; to[j] = min(n + 1, j + a[j]); } else{ cnt[j] = cnt[j + a[j]] + 1; to[j] = min(n + 1, to[j + a[j]]); } } }}void modify(int pos, int val){ a[pos] = val; for (int i = pos; i >= L[belong[pos]]; i--){ if (i + a[i]>R[belong[pos]]){ cnt[i] = 1; to[i] = min(i + a[i], n + 1); } else{ cnt[i] = cnt[i + a[i]] + 1; to[i] = min(to[i + a[i]], n + 1); } }}void query(int pos, int &ans, int &preidx){ ans = 0; for (int i = pos; i <= n; i = to[i]){ ans += cnt[i]; preidx = i; //记录最后弹出去前的位置 } for (int i = preidx; i <= n; i = i + a[i]){ //暴力模拟最后在哪个位置弹出去了 preidx = i; }}int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); while (~scanf("%d%d", &n, &q)){ for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } build(); int type, pos, v, ans, idx; for (int i = 1; i <= q; i++){ scanf("%d", &type); if (type == 0){ scanf("%d%d", &pos, &v); modify(pos, v); } else{ scanf("%d", &pos); query(pos, ans, idx); printf("%d %d\n", idx, ans); } } }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}