A22728题解

题意简述

初始数列是空的，一共有M次操作，给定常数D。

1. A n插入操作：计算(n+t) mod D，t是最近一次查询输出的结果，没有查询则t=0，将计算结果添加到数列末尾。n可能是负数，模运算结果必须是非负数。
2. Q L查询操作：找出数列末尾L个数字里面的最大值，输出该值，把输出值保存到t。
   数据规模较大，暴力遍历查询会超时，采用线段树求解。

算法选择：线段树维护区间最大值

线段树可以支持单点修改、区间查询最大值，两种操作时间复杂度都是$O(\log N)$。
本题只会在数组尾部添加元素，相当于不断做单点赋值；查询是求后缀一段区间的最大值，完美匹配线段树能力。

变量说明

1. ed：记录当前数列一共有多少个元素，也就是末尾元素的下标，初始等于0。每执行一次A操作，ed ++。
2. t：保存上一次查询得到的答案，初始为0。
3. D：题目给定取模常数。
4. tree[]：线段树数组，开4倍最大数组长度，存储区间最大值。

插入操作 A n

1. 计算数值：val = ((n + t) % D + D) % D。

C++中负数对D取模结果会是负数，+D再取模把结果修正为0~D‑1之间非负数字。

2. ed自增，代表新元素放在下一个位置。
3. 调用线段树单点更新函数，把下标ed位置赋值为val。

查询操作 Q L

1. 当前总元素个数是ed，末尾L个元素对应的区间是：左端点 ed‑L+1，右端点 ed。
2. 调用线段树区间最大值查询，查询[ed‑L+1,ed]的最大值。
3. 将得到的最大值赋值给t，输出这个数值。

线段树函数逻辑

1. update更新函数：单点修改，找到对应下标位置，修改叶子节点，向上回溯更新各个父节点保存区间最大值。
2. query查询函数：给定查询左右边界，如果当前节点区间完全被查询区间包含，直接返回该节点存的最大值；否则递归左右子树，合并返回左右区间的最大结果。

复杂度分析

假设操作总次数M，数组最大长度N。
每次插入、查询操作花费$O(\log N)$，整体时间复杂度 $O(M\log N)$。空间复杂度\(O(4N)\)，满足题目内存限制。

易错点

1. 负数取模处理，不能直接写(n+t)%D，否则会出现负数存入数组，答案出错。
2. 查询区间左边界计算：ed‑L+1，不要写成ed‑L，下标从1开始。
3. t是查询输出的结果，只有Q操作才会修改t，A操作不改变t；没有查询时t=0。
4. 大数据输入，必须开启输入输出加速，否则会超时。

和样例模拟

输入样例：5 100
M=5，D=100；ed=0，t=0

1. A 96：val=((96+0)%100+100)%100=96；ed变为1；线段树位置1赋值96。
2. Q 1：查询区间[1‑1+1,1]即[1,1]，最大值96；输出96，t=96。
3. A 97：val=((97+96)%100+100)%100=93；ed=2；位置2赋值93。
4. Q 1：查询区间[2‑1+1,2]即[2,2]，最大值93；输出93，t=93。
5. Q 2：查询区间[2‑2+1,2]即[1,2]，max(96,93)=96；输出96，t=96。
   输出结果与样例完全吻合。

对比其他做法

1. 单调栈+二分：均摊\(O(M)\)，常数更小；但是需要维护栈以及下标，逻辑相对绕。
2. 线段树：逻辑直观，单点修改区间查询模板直接套用，不容易写错，适合竞赛写题。
3. ST表：ST表适合静态数组，本题动态在尾部增加，虽然可以动态扩展ST表，代码处理麻烦，不如线段树方便。

最后，来看代码：

/*
This code was automatically submitted by chhongzh's bot!
                                                        
                 More info: jj66amvxo[at]mozmail[dot]com
                          Submit At: 2026-05-20 17:26:15
                                 Time Used: 670.597037ms

*/



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll tree[N << 2];

void update(int l, int r, int rt, int pos, ll val) {
    if (l == r) {
        tree[rt] = val;
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)update(l, mid, rt << 1, pos, val);
    else update(mid + 1, r, rt << 1 | 1, pos, val);
    tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}

ll query(int l, int r, int rt, int L, int R) {
    if (L <= l && r <= R) {
        return tree[rt];
    }
    int mid = l + r >> 1;
    if (R <= mid)return query(l, mid, rt << 1, L, R);
    else if (L > mid)return query(mid + 1, r, rt << 1 | 1, L, R);
    else return max(query(l, mid, rt << 1, L, R), query(mid + 1, r, rt << 1 | 1, L, R));
}

void solve() {
    int n, mod;
    cin >> n >> mod;
    int ed = 0;
    ll t = 0;
    while (n--) {
        char op;
        ll val;
        cin >> op >> val;
        if (op == 'A') {
            update(1, N - 1, 1, ++ed, ((val + t) % mod + mod) % mod);
        } else {
            ll ans = query(1, N - 1, 1, ed - val + 1, ed);
            t = ans;
            cout << t << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    solve();
}