#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 6;
int n, mod, t;
vector<int>v;
int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
signed main() {
	n = read(), mod = read();
	while (n--) {
		char ch = getchar();
		int x;
		x = read();
		if (ch == 'A') {
			x += t;
			x %= mod;
			v.push_back(x);
		} else {
			x = (int)v.size() - x;
			auto it = max_element(v.begin() + x, v.end());
			cout << *it << endl;
			t = *it;
		}
	}
	return 0;
}

线段树

对每个数预留一个位置，之后的新增实际上就是修改，这样就是一个单点修改，区间查询问题。

#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
typedef long long ll;
using namespace std;
const int N = 2e5 + 1, inf = 0x3f3f3f3f;
int n, m, p;
struct Node {
    int l, r, v;
} tr[N << 2];

void pushup(int u) {
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
}
void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
int main() {
    cin >> m >> p, build(1, 1, m);
    int last = 0, t; char op;
    while (m--) {
        cin >> op >> t;
        if (op == 'Q') {
            last = query(1, n - t + 1, n);
            cout << last << endl;
        } else {
            modify(1, ++n, (1ll * t + last) % p);
        }
    }
    return 0;
}