本文写于 2020年02月24日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

计蒜客 蒜头君的任务

题目描述

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

  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;
}
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论