codeforces 13E . Holes 分块

题目链接

nextt数组表示这个位置的下一个位置。

cnt数组表示这个位置 i 到nextt[i]可以弹几次。

end[i] 表示在从 i 弹出去的情况下， 最后一个位置是哪里。

然后就看代码吧。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

const int maxn = 1e5 + ;

int a[maxn], cnt[maxn], nextt[maxn], pos[maxn], block[maxn], n;

void update(int x, int y) {

    if(y >= n) {

        nextt[x] = n+;

        cnt[x] = ;

        pos[x] = x;

    } else {

        if(block[x] == block[y]) {

            nextt[x] = nextt[y];

            cnt[x] = cnt[y] + ;

        } else {

            nextt[x] = y;

            cnt[x] = ;

        }

        pos[x] = pos[y];

    }

}

void query(int x) {

    int i, ans = ;

    for(i = x; ; i = nextt[i]) {

        ans += cnt[i];

        if(nextt[i] >= n) {

            i = pos[i];

            break;

        }

    }

    printf("%d %d\n", i+, ans);

}

int main()

{

    int m, sign, x, y;

    cin>>n>>m;

    int BLOCK = sqrt(n);

    for (int i = ; i < n; i++) {

        scanf("%d", a + i);

        block[i] = i / BLOCK;

    }

    for (int i = n-; i >= ; i--) {

        update(i, i + a[i]);

    }

    while (m--) {

        scanf("%d", &sign);

        if(sign) {

            scanf("%d", &x);

            query(x-);

        } else {

            scanf("%d%d", &x, &y);

            x--;

            a[x] = y;

            int l = block[x] * BLOCK;

            int r = l + BLOCK;

            r = min(n, r);

            for(int i = r-; i >= l; i--) {

                update(i, i + a[i]);

            }

        }

    }

    return ;

}