「洛谷P3202」[HNOI2010]弹飞绵羊解题报告

P3203 [HNOI2010]弹飞绵羊

题目描述

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入输出格式

输入格式：

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

输出格式：

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

输入输出样例

输入样例#1：

输出样例#1：

2
3

说明

对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

思路

我们运用分块思想，把序列分成\(\sqrt{n}\)块，每个点\(i\)计录两个值\(c[i],s[i]\)，表示再弹\(s[i]\)次第一次落到该块外，且落到\(c[i]\)的位置。预处理是\(O(N)\)的，每次修改、查询都是\(O(\sqrt N)\)的，所以复杂度是正确的（虽然8e7有点悬）。具体看代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005

int N, M;
int a[MAXN], b[MAXN], n;
int c[MAXN], s[MAXN];

int main(){
    scanf( "%d", &N ); n = (int)sqrt(N);
    for ( int i = 1; i <= N; ++i ) scanf( "%d", &a[i] ), b[i] = ( i - 1 ) / n + 1;//记录每个点所属的块
    for ( int i = N; i >= 1; ){//倒序复杂度是O(N)，正序是O(n^1.5)
        int t(b[i]), j(i);
        while( b[j] == t ){
            if ( j + a[j] > i ) c[j] = j + a[j], s[j] = 1;//一次就弹出该块
            else c[j] = c[j + a[j]], s[j] = s[j + a[j]] + 1;//递推思想
            j--;
        }
        i = j;
    }
    
    int op, x, y; scanf( "%d", &M );
    while ( M-- ){
        scanf( "%d%d", &op, &x ); x++;
        if ( op & 1 ){
            int ans(0);
            for ( int i = x; i <= N; ) ans += s[i], i = c[i];//只要一直弹即可。每次弹都会经过一整个块，因此每次复杂度为O(N^0.5)
            printf( "%d\n", ans );
        }else{
            scanf( "%d", &y );
            a[x] = y; int t(b[x]), j(x);

            while( b[j] == t ){//只要修改该块内即可，复杂度也为O(N^0.5)
                if ( j + a[j] > x ) c[j] = j + a[j], s[j] = 1;
                else c[j] = c[j + a[j]], s[j] = s[j + a[j]] + 1;
                j--;
            }
        }
    }
    return 0;
}