线段树 & 单调栈

#include <cstdio>
#include <cctype>

const int N = 5000010;

int mod;

inline int read() {
    int f = 0, flag = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') flag = -1;
        c = getchar();
    }
    while (isdigit(c)) f = f * 10 + c - 48, c = getchar();
    return f * flag;
}

int max(const int &a, const int &b) {
    return a > b ? a : b;
}

struct SegmentTree
{
    int mx[N * 4];

    void pushup(int u) {
        mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
    }

    void modify(int u, int l, int r, int x, int v) {
        if (l == r) mx[u] = (1LL * mx[u] + v) % mod;
        else {
            int mid = l + r >> 1;
            if (x <= mid) modify(u << 1, l, mid, x, v);
            else modify(u << 1 | 1, mid + 1, r, x, v);
            pushup(u);
        }
    }

    int query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return mx[u];
        else {
            int mid = l + r >> 1;
            int res = 0;
            if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
            if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
            return res;
        }
    }
} smt;

int main() {
    int n = read();
    mod = read();
    int t = 0;
    int len = 0;
    while (n--) {
        char op = getchar();
        while (op != 'A' && op != 'Q') op = getchar();
        int x = read();
        if (op == 'A') {
            smt.modify(1, 1, 5000000, ++len, (1LL * x + t) % mod);
        }
        else {
            t = smt.query(1, 1, 5000000, len - x + 1, len);
            printf("%d\n", t);
        }
    }
    return 0;
}

#include <cstdio>
#include <cctype>

const int N = 5000010;

int mod;

inline int read() {
    int f = 0, flag = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') flag = -1;
        c = getchar();
    }
    while (isdigit(c)) f = f * 10 + c - 48, c = getchar();
    return f * flag;
}

struct Num
{
    int pos, val; 
} st[N];
int top;

int main() {
    int n = read();
    mod = read();
    int t = 0, len = 0;
    for (int i = 1; i <= n; ++i) {
        char op = getchar();
        while (op != 'A' && op != 'Q') op = getchar();
        int x = read();
        if (op == 'A') {
            x = (1LL * x + t) % mod;
            while (top && x >= st[top].val) --top;
            st[++top] = {++len, x};
        }
        else {
            x = len - x + 1;
            int l = 0, r = top;
            while (l < r) {
                int mid = l + r >> 1;
                if (st[mid].pos < x) l = mid + 1;
                else r = mid;
            }
            t = st[l].val;
            printf("%d\n", st[l].val);
        }
    }
    return 0;
}