A2447 [JSOI2008] 最大数【无数据】

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

using ll = long long;

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

    int M;
    ll D;
    cin >> M >> D;

    vector<ll> a;          // 序列里的所有数
    vector<int> stk;       // 单调栈：下标递增、值严格递减
    ll last = 0;           // 最近一次查询的答案 t

    for (int i = 0; i < M; i++) {
        char op;
        ll v;
        cin >> op >> v;
        if (op == 'A') {
            ll x = ((v + last) % D + D) % D;
            a.push_back(x);
            // 栈里比 x 小的（或相等的）都不再可能成为后缀最大值
            while (!stk.empty() && a[stk.back()] <= x) stk.pop_back();
            stk.push_back((int)a.size() - 1);
        } else {
            int L = (int)v;
            int size = (int)a.size();
            int pos = size - L;           // 要查询的是下标 >= pos 的后缀
            // 栈里第一个下标 >= pos 的元素，就是这个后缀的最大值
            int lo = 0, hi = (int)stk.size() - 1, ansIdx = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (stk[mid] >= pos) {
                    ansIdx = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            last = a[stk[ansIdx]];
            cout << last << "\n";
        }
    }
    return 0;
}