首页 > 其他 > 详细

BZOJ2002 [HNOI2010]弹飞绵羊

时间:2018-11-18 14:44:34      阅读:164      评论:0      收藏:0      [点我收藏+]

题目蓝链

Description

\(n\)个弹簧排成一列,每一个弹簧都会给定一个向后弹射的距离,然后需要支持两个操作

  1. 查询从某个弹簧开始需要弹多少次后,就会弹到第\(n\)个弹簧之后

  2. 修改某个弹簧的向后弹射距离

Solution

考虑分块,每一个块中维护每一个位置要跳多少次才能跳出这个块,跳出去后是落在那个位置

查询直接\(\mathcal{O}(\sqrt n)\)一个块一个块的模拟去跳,修改就更新修改位置所在块的信息就可以了

Code

#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef pair<int, int> pii;

inline int read() {
    int sum = 0, fg = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) fg = -1;
    for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
    return fg * sum;
}

const int maxn = 2e5 + 10;
const int B = 400;

int n, m, blks, f[maxn], S[maxn], T[maxn];

int pos(int x) { return x <= n ? (x - 1) / B + 1 : blks + 1; }

int main() {
    freopen("sheep.in", "r", stdin);
    freopen("sheep.out", "w", stdout);

    n = read();
    for (int i = 1; i <= n; i++) f[i] = read() + i;

    blks = (n - 1) / B + 1;
    for (int i = 1; i <= blks; i++) {
        int e = min(i * B, n), tmp = (i - 1) * B;
        for (int j = e; j > tmp; j--)
            if (f[j] <= e) S[j] = S[f[j]] + 1, T[j] = T[f[j]];
            else S[j] = 1, T[j] = f[j];
    }

    m = read();
    while (m--) {
        int op = read();
        if (op == 1) {
            int x = read() + 1, ans = 0;
            while (pos(x) <= blks) ans += S[x], x = T[x];
            printf("%d\n", ans);
        }
        if (op == 2) {
            int x = read() + 1, p = pos(x);
            f[x] = read() + x;
            int tmp = (p - 1) * B, e = min(p * B, n);
            for (int i = x; i > tmp; i--) {
                if (f[i] <= e) S[i] = S[f[i]] + 1, T[i] = T[f[i]];
                else S[i] = 1, T[i] = f[i];
            }
        }
    }

    return 0;
}

Summary

这道题代码细节是真的多,我打之前没有想清一些的细节。所以我一边打一边想,调了我一个小时

一定要注意区分数组的下标和实际位置

BZOJ2002 [HNOI2010]弹飞绵羊

原文:https://www.cnblogs.com/xunzhen/p/9977779.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!