形式化题目

维护一个初始为空的序列 $a$，按给定顺序处理 $m$ 个操作，只有两种：

• 追加 $A\ t$：在末尾写入 $(t + a) \bmod p$，其中 $a$ 是上一次询问的答案（还没询问过时 $a = 0$）；
• 询问 $Q\ L$：输出当前序列最后 $L$ 个数的最大值，即下标区间 $[\,n - L,\ n - 1\,]$（0-based，$n$ 为当前长度）上的最大值。

序列只在末尾增长，没有修改与删除；而每个新元素的值又依赖上一次询问的答案，所以操作必须严格按输入顺序在线处理，无法离线重排。题目保证第一个操作是追加，且每次询问的 $L$ 合法（$L > 0$ 且不超过当前长度）。

样例的取值依赖可以逐步展开：A 97 追加 $97$（此时还没有答案，$a = 0$）；Q 1 答 $97$，于是 $a = 97$；接着 A 17 追加 $(17 + 97) \bmod 100 = 14$，再 A 63 追加 $(63 + 97) \bmod 100 = 60$，最后一次 A 99 在答案 $a = 97$ 之后追加 $(99 + 97) \bmod 100 = 96$。最终序列是 $97, 14, 60, 96$，六个询问的答案依次为 $97, 97, 97, 60, 60, 97$，与题面输出一致。

正解

思路

一句话本质：把"最后 $L$ 个数的最大值"变成两次查表——按 $2$ 的幂把序列分层，预存"以某个位置结尾、长度 $2^k$ 的块"的最大值；追加时每层最多补一项，询问时用两段重叠的块夹住后缀。

朴素做法：每次 Q L 从下标 $n - L$ 扫到 $n - 1$ 维护最大值，单次 $O(L)$。最坏情况 $m$ 次询问都问全后缀，总代价 $O(m^2) = 4 \times 10^{10}$ 次比较，远超 1000 ms。

瓶颈：不同询问反复比较同一批后缀元素。但序列只追加不修改——历史区间上的比较结果永不失效，完全可以预存下来复用；又因为 $\max$ 满足幂等性 $\max(S \cup S) = \max(S)$，区间允许重叠地拆成两段再取最大，这正是 RMQ 能两段作答的根本原因。

分层预存：只存长度为 $2$ 的幂的块。记 $st[k][i]$ 表示以 $i$ 结尾、长度 $2^k$ 的区间的最大值，它恰好由两个长度 $2^{k-1}$ 的半段拼成：

本题查询的永远是"以末尾结尾的后缀"，所以按区间结尾分层比按起点分层更顺手：新元素落在下标 $pos$，它只影响"以 $pos$ 结尾"的块，每次追加把 $2^k \leqslant size$ 的层各补一个表项即可（$size$ 为追加后的长度），建表随追加在线增量完成。样例最终序列 $97, 14, 60, 96$ 的在线 ST 表如下（行 = 层 $k$，列 = 结尾下标）：

读表要点：每格 = 上一层同结尾的格（后半段）与上一层左移 $2^{k-1}$ 列的格（前半段）取 max——结尾 1 的 $97 = \max(97, 14)$、结尾 2 的 $60 = \max(14, 60)$、结尾 3 的 $97 = \max(96, 97)$；空格表示序列还不够长、放不下该长度的整块，这正是“层只在 $2^k \leqslant size$ 时存在”的含义。

查询两段覆盖：询问最后 $L$ 个数，即区间 $[\,size - L,\ size - 1\,]$。取 $k = \lfloor \log_2 L \rfloor$、$span = 2^k$（代码里用 bit_length 求，不碰浮点），取两段长度都是 $span$ 的块：

由 $2^k \leqslant L < 2^{k+1}$：两段都不超出询问区间；又 $2 \cdot span \geqslant L + 1$ 保证右段左端 $\leqslant$ 左段右端，两段相交，并集恰为 $[\,size - L,\ size - 1\,]$，$\max$ 幂等所以重叠无害。以样例 Q 3 为例（序列 $97, 14, 60$，$L = 3$，$k = 1$，$span = 2$）：第一段覆盖 $[1, 2]$ 得 $60$，第二段覆盖 $[0, 1]$ 得 $97$，取 max 得 $97$。

在线依赖：取值依赖只影响"追加什么值"（last_ans 参与取模），不影响"怎么查"；操作按输入顺序原样处理即可。边界上，$L = 1$ 时 $k = 0$、两段同为最后一个元素；$L$ 恰为 $2$ 的幂时两段重合成一段；$L = size$ 时左段存下标为 $0$，都在表内。

代码

st[k][j] 存下标 $j$ 对应结尾位置 $j + 2^k - 1$（该层只在序列够长后才存在，存下标 = 位置 - $2^k$ + 1）；追加分支的 while 循环是增量建层递推式，询问分支三行就是上面的两段覆盖；last_ans 保存上一次询问答案，供下一个 A 取模使用。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 17:36
# update_at: 2026-09-30 17:36

import sys


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    op_count, mod = int(next(data)), int(next(data))

    # 在线 ST 表：st[k][j] 表示以下标 j + 2^k - 1 结尾、长度 2^k 的区间的最大值。
    # 第 k 层只在序列够长（下标 >= 2^k - 1）后才存在，故存下标 = 位置 - 2^k + 1。
    st: list[list[int]] = [[]]
    out: list[str] = []
    size = 0        # 当前序列长度
    last_ans = 0    # 上一次询问的答案 a，还没询问过时为 0

    for _ in range(op_count):
        op = next(data)
        arg = int(next(data))

        if op == b'A':
            st[0].append((arg + last_ans) % mod)   # 长度 1 的区间就是新元素本身
            pos = size                             # 新元素的下标
            size += 1

            k = 1
            while (1 << k) <= size:                # 区间必须整体落在序列内
                if k == len(st):                   # 序列长度越过 2^k，新建一层
                    st.append([])
                half = 1 << (k - 1)
                # 前半段 [pos-2*half+1, pos-half] 与后半段 [pos-half+1, pos] 各取最大再合并
                st[k].append(max(st[k - 1][pos - 2 * half + 1], st[k - 1][pos - half + 1]))
                k += 1
        else:
            # 询问最后 L 个数：用首尾两段长 2^k <= L 的区间夹住 [size-L, size-1]
            k = arg.bit_length() - 1
            span = 1 << k
            tail = st[k][size - span]               # 以末尾结尾的 2^k 段
            head = st[k][size - arg]                # 从询问左端起的 2^k 段
            last_ans = max(tail, head)
            out.append(str(last_ans))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:39
 * update_at: 2026-10-05 07:39
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXM = 200005; // m 的上限
const int MAXK = 20;     // 2^18 > 2*10^5，够放下所有层

// 在线 ST 表：st[k][j] 表示以下标 j + 2^k - 1 结尾、长度 2^k 的区间的最大值。
// 第 k 层只在序列够长后才存在，所以存下标 = 结尾位置 - 2^k + 1；
// len[k] 记录第 k 层当前已存了几个表项，新增表项就放在下标 len[k] 处。
ll st[MAXK][MAXM];
int len[MAXK];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll m, p;
    cin >> m >> p;

    ll size = 0;     // 当前序列长度
    ll last_ans = 0; // 上一次询问的答案 a，还没询问过时为 0

    for (ll i = 1; i <= m; i++) {
        char op;
        ll arg;
        cin >> op >> arg;

        if (op == 'A') {
            // 长度 1 的区间就是新元素本身
            st[0][len[0]] = (arg + last_ans) % p;
            len[0]++;

            ll pos = size; // 新元素的下标
            size++;

            // 增量补层：新元素只影响“以 pos 结尾”的块
            for (int k = 1; (1LL << k) <= size; k++) {
                ll half = 1LL << (k - 1); // 半段长度
                // 两段合成：以 pos-half 结尾的前半段 + 以 pos 结尾的后半段
                st[k][len[k]] = max(st[k - 1][pos - 2 * half + 1],
                                    st[k - 1][pos - half + 1]);
                len[k]++;
            }
        } else {
            // 询问最后 arg 个数：用两段长 2^k <= arg 的块夹住 [size-arg, size-1]
            int k = 0;
            while ((1LL << (k + 1)) <= arg) {
                k++;
            }
            ll span = 1LL << k;

            ll tail = st[k][size - span]; // 以末尾结尾的 2^k 段
            ll head = st[k][size - arg];  // 从询问左端起头的 2^k 段
            last_ans = max(tail, head);
            cout << last_ans << '\n';
        }
    }

    return 0;
}

复杂度

• 时间复杂度：追加补 $\lfloor \log_2 n \rfloor + 1$ 层、每层一次 max，全程 $O(m \log m)$；询问两次查表 + 一次 max，$O(1)$。与 C++ 线段树/ST 表解法同阶，查询更优。
• 空间复杂度：$O(m \log m)$ 个表项（第 $k$ 层 $\max(0,\ m - 2^k + 1)$ 个，$m = 2 \times 10^5$ 时合计约 $3.4 \times 10^6$）；大量表项是对同一个 int 对象的引用，实测峰值 62.4 MB，低于 128 MB 限制。

总结

后缀 RMQ 在线化：序列只追加不修改 → 历史块可预存；$\max$ 幂等 → 区间允许重叠地两段覆盖。于是按"区间结尾"分层维护 $2^k$ 块最大值，追加时每层增量补一项 $O(\log m)$，询问时 bit_length 取 $k$、两段查表取 max 得 $O(1)$，总复杂度 $O(m \log m)$。取值的在线依赖（$(t + a) \bmod p$ 中的 $a$ 是上一次询问答案）只需一个 last_ans 变量，按输入顺序处理自然满足。实测 8 组真实数据全部一致，最慢一组 0.263 s、峰值内存 62.4 MB，相对 1000 ms / 128 MB 的限制余量充足（本地按 python-oj-short 规则放宽到 20 s 限时、不限内存验证）。