原题链接

题解1：单调栈+并查集？

单调栈特性：栈内元素大小和序号由栈底到栈顶具有单调性，本题大小单调减，序号单调增
维护：新元素入栈时，栈内剩余的所有小于该元素的元素出栈，并视新元素为集合首领，然后新元素入栈
查询：查询集合首领即可

code1

#define ll long long
#include<bits/stdc++.h>
using namespace std;

struct num {
    ll pos;
    ll val;
};

ll fa[200005] = {0};

ll finds(ll now) {
    return fa[now] = (now == fa[now] ? now : finds(fa[now]));
}

vector<ll> a;

inline void read(ll &x) {  
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48); 
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    ll m, d;
    read(m); read(d);

    for(ll i = 0; i < m; i++) fa[i] = i;

    ll t = 0, len = 0;
    stack<num> q;
    while(m--) {
        char op;
        ll n;
        scanf(" %c", &op);
        read(n);
        if(op == 'Q') {
            n = a.size() - n ;
            write(a[finds(n)]);
            putchar('\n');
            t = a[finds(n)];
        } else {
            a .push_back (n = (n + t) % d);
            while(!q.empty() && n >= q.top().val) {
                ll now = q.top().pos;
                fa[finds(now)] = a.size()-1;
                q.pop();
            }
            q.push({a.size()-1, n});
        }
    }
    return 0;
}

题解2

st表，不过是向左延申的st表

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;

// Custom input and output functions
inline void read(ll &x) {  
    x = 0;
    ll flag = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flag = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48); 
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

ll len = 0;
vector<vector<ll>> f(200005, vector<ll>(35, 0)); // Using vector for f
ll a[200005] = {0}; // Keeping a as an array since it's directly accessed by index and there's no mention of dynamic resizing

void change() {
    f[len][0] = a[len];
    for (ll i = 1; (1LL << i) <= len; i++) {
        f[len][i] = max(f[len][i - 1], f[len - (1LL << (i - 1))][i - 1]);
    }
}

int main() {
    ll n, d;
    read(n); // Using custom read function
    read(d); // Using custom read function
    ll t = 0;
    while (n--) {
        char op;
        cin >> op; // Keeping cin for char as it's simple and efficient
        ll x;
        read(x); // Using custom read function
        if (op == 'A') {
            a[++len] = (x + t) % d;
            change();
        } else {
            ll ans = 0;
            ll l = len - x + 1; // Ensuring correct value of l
            ll r = len;
            for (ll j = 31; j >= 0; j--) {
                if ((1LL << j) <= r - l + 1) { // Using 1LL to ensure long long calculation
                    ans = max(ans, f[r][j]);
                    r -= 1LL << j; // Adjusting r for the new position
                }
            }

            write(ans); // Using custom write function
            putchar('\n'); // To end the line after output
            t = ans;
        }
    }
    return 0;
}