计蒜客 蒜头君的任务

题目描述

蒜头君的上司给蒜头君布置了一个任务，蒜头君维护一个数列，要求提供以下两种操作：

1. 查询操作。

语法：Q L

功能：查询当前数列中末尾 $L$ 个数中的最大的数，并输出这个数的值。

1. 插入操作。

语法：A n

功能：将 $n$ 加上 $t$，其中 $t$ 是最近一次查询操作的答案（如果还未执行过查询操作，则 $t = 0$)，并将所得结果对一个固定的常数 $D$ 取模，将所得答案插入到数列的末尾。

初始时数列是空的，没有一个数。

样例

样例输入

第一行两个整数，$M$ 和 $D$，其中 $M$ 表示操作的个数($M \leq 200000$)，$D$ 如上文中所述，满足 $D$ 在 $32$ 位整型范围内。

接下来 $M$ 行，查询操作或者插入操作。

5 100
A 96
Q 1
A 97
Q 1
Q 2

样例输出

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 $L$ 个数的最大数。

96
93
96

算法与数据结构

树状数组
区间最值

题解

这道题就是直接套用树状数组区间最值的模板。

完整代码

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200007;
int A[MAX_N] = {0}; // 输入数据 A
int C[MAX_N] = {0}; // 树状数组 C

int lowBit(int x) {
    return x & -x; // return x & (x ^ (x - 1))
}

// 注意哪里是 A 哪里是 C
int getMax(int l, int r) {
    int ret = A[r];
    while (l <= r) {
        ret = max(ret, A[r]);
        for (--r; r - l >= lowBit(r); r -= lowBit(r))
            ret = max(ret, C[r]);
    }
    return ret;
}

void change(int r) {
    C[r] = A[r];
    for (int i = 1; i < lowBit(r); i <<= 1)
        C[r] = max(C[r], C[r - i]);
}

int main() {
    int M, D;
    int r = 1; // 树状数组下标从 1 开始
    int t = 0;
    scanf("%d%d", &M, &D);
    for (int i = 0; i < M; i++) {
        char op;
        scanf("\n%c", &op);
        if (op == 'Q') {
            int l;
            scanf("%d", &l);
            t = getMax(r - l, r - 1); // 最后 L 个数是 r - l 到 r - 1，不是从 l 到 r
            printf("%d\n", t);
        } else {
            int n;
            scanf("%d", &n);
            A[r] = (n + t) % D; // 要记录 A[r]
            change(r);
            r++; // r 其实是作为数列最右端的标识
        }
    }

    return 0;
}