算法|题解

计蒜客 – 蒜头君的任务

凝神长老 · 2月24日 · 2020年 · 763次已读

计蒜客 蒜头君的任务

题目描述

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

  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;
}
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论