[JSOI2008] 最大数

BIT

注意这个题目,只在尾插入值, 所有我的代码和 Rbook - 树状数组区间最值有点区别,但核心思想是一样的

区别在:认为: bit数组的初始值为-INF, update 不停的更新父亲(少写代码),自己体会一下,

因为我们是按顺序追加 (Append) 元素的，之前的元素已经正确更新了 tree 数组中的父节点。所以，当我们加入新元素 val 时，只需要在现有 tree 值的基础上取 max 即可，千万不能直接赋值覆盖。

同时，由于 tree 数组一开始被初始化为极小值 (INF)，第一次遇到新位置时，max(INF, val) 会自动变成 val，逻辑是自洽的。

代码

cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXM = 200005;
const long long INF = -2e18; // 极小值，足够小即可

// tree[i] 维护 [i - lowbit(i) + 1, i] 的最大值
long long tree[MAXM];
long long a[MAXM]; // 原数组，用于查询时如果区间不匹配则降级查找
int M;
long long D;
int cnt = 0; // 当前数组实际长度

int lowbit(int x) {
    return x & -x;
}

// 修复后的 update：只做 max 更新，绝不覆盖
// 仅适用于 Append 模式（从左到右依次填充）
void update(int x, long long val) {
    for (int i = x; i <= M; i += lowbit(i)) {
        tree[i] = max(tree[i], val);
    }
}

// 区间查询 [L, R]
long long query(int L, int R) {
    long long res = INF;
    while (R >= L) {
        // 如果 tree[R] 覆盖的左边界没有越过 L，说明这一整段都在查询范围内
        if (R - lowbit(R) + 1 >= L) {
            res = max(res, tree[R]);
            R -= lowbit(R); // 跳过这一大段
        } else {
            // 如果 tree[R] 覆盖范围太长，超出了 L，就不能用 tree[R]
            // 只能使用原数组 a[R] 这个单点，然后向前挪一步
            res = max(res, a[R]);
            R--;
        }
    }
    return res;
}

int main() {
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> M >> D;

    // 初始化：tree 必须全部初始化为极小值
    fill(tree, tree + MAXM, INF);
    // a 数组其实不需要显式初始化为 INF，因为我们是按 cnt 指针读写的，但为了安全也可以初始化
    fill(a, a + MAXM, INF);

    long long t = 0; // 记录上一次查询结果

    for (int i = 0; i < M; i++) {
        char op;
        long long n; // 注意：输入的 n 可能是负数，且需要 long long
        cin >> op >> n;

        if (op == 'A') {
            // 题目公式：(n + t) % D
            long long val = (n + t) % D;
            cnt++;
            a[cnt] = val;     // 必须存原值
            update(cnt, val); // 更新 BIT
        } else {
            int L = n; // 这里 n 代表题目中的长度 L
            if (cnt == 0) {
                t = 0;
            } else {
                // 查询最后 L 个数 -> 区间 [cnt - L + 1, cnt]
                t = query(cnt - L + 1, cnt);
            }
            cout << t << "\n";
        }
    }

    return 0;
}

重点细节复盘

为什么这个能 AC？
- Update 修复：tree[i] = max(tree[i], val) 保证了新加入的数 val 只是去更新它所属的区间，而不会把那个区间里“以前的较大值”给抹除。
- Append 模式的特殊性：因为我们是 1, 2, 3... 这样填坑的，当我们填 cnt 时，cnt 左边的所有节点都已经处于“正确维护了最大值”的状态。所以我们只需要向右上传新的最大值即可。
BIT 做 RMQ 的局限性
- 这套逻辑只适合“末尾追加”或者“静态数组”。
- 如果是“中间修改一个值”（比如把第 3 个数改大或改小），这套 BIT 代码是无法处理的（改小的情况特别难处理，因为 max 没法逆运算），那时候就必须用线段树。
- 但对于这道题，BIT 是完美的，且常数极小。

线段树

TODO

单调栈

TODO: https://www.luogu.com.cn/article/n4jpwmmk

目录

BIT

代码

重点细节复盘

线段树

单调栈