并查集：最 diao 的数据结构

#include <cstdio>
using namespace std;

const int MAXN = 2e6 + 10;
int fa[MAXN], val[MAXN];
int n;

void init()
{
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int Find(int x)
{
    while (x != fa[x]) {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}

void merge(int x, int y)
{
    x = Find(x), y = Find(y);
    fa[y] = x;
}

int main()
{
    // freopen("5.in", "r", stdin);
    // freopen("5.out", "w", stdout);
    int mod;
    scanf("%d%d", &n, &mod);
    init();
    int top = 0;
    long long rec = 0;
    // val[0] = -0x3f3f3f3f;
    while (n--) {
        char op = getchar();
        while (op != 'A' && op != 'Q') {
            op = getchar();
        }
        int x;
        scanf("%d", &x);
        switch (op) {
            case 'A':
                val[++top] = (rec + x) % mod;
                while (val[Find(Find(top) - 1)] < val[Find(top)]) {
                    val[Find(Find(top) - 1)] = val[Find(top)];
                    merge(Find(top) - 1, Find(top));
                }
                break;
            case 'Q':
                printf("%d\n", rec = val[Find(top - x + 1)]);
                break;
            default:
                printf("ERROR\n");
                return 0;
        }
    }
    return 0;
}