火星饭店

题目描述

lzh 在火星开了一家饭店，为了吸引顾客，饭店会不定期在菜谱中加入新菜，每个菜都有一个美味度 $l(0\le l < p)$。

饭店使用手机进行点餐，手机上展示的菜谱会按照更新的顺序逆序排列。由于不同顾客的手机屏幕分辨率大小不同，所以能够显示在第一屏的菜谱的数量也不同。根据调查发现，火星用户只会在第一屏的菜品中选择美味度最高的购买。

现在按照时间顺序输入 $m$ 个添加菜品或顾客点菜的操作，请输出每位点菜顾客所点的菜的美味度。

输入格式

第一行有两个正整数 $m,p$，意义如题目描述；

接下来 $m$ 行，每一行表示一个操作。

• 如果该行的内容是 Q L，则表示有顾客进行了点菜，该顾客的手机屏幕可以显示 $L$ 个菜品；
• 如果是 A t，则表示加入了新的菜品，菜品的美味度是 $(t+a)\bmod p$。
  • $t$ 是输入的参数
  • $a$ 是在这个添加操作之前最后一个点菜操作的答案（如果之前没有点菜操作，则 $a = 0$）。

数据保证第一个操作一定是添加菜品。在顾客点菜时，$L\gt 0$ 且不超过当前已有菜品的数量。

输出格式

对于每一个点菜操作，输出一行。该行只有一个数，即当前屏幕中美味度最大的菜品的美味度。

样例

输入

10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99

输出

97
97
97
60
60
97

数据范围

对于全部数据，$1\le m\le 2\times 10^5,1\le p\le 2\times 10^9,0\le t\lt p$。

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

const int MAXN = 300005;
int n, dat[2 * MAXN - 1];

void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;
    for (int i = 0; i < 2 * n - 1; ++i) dat[i] = INT_MIN;
}

void update(int k, int a) {
    k += n - 1, dat[k] = a;
    while (k > 0) k = (k - 1) / 2, dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
}

int query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return INT_MIN;
    if (a <= l && r <= b) return dat[k];
    int vl = query(a, b, k * 2 + 1, l, (l + r) / 2), vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return max(vl, vr);
}

int main() {
    int m, p, a = 0, t, cnt = 0;
    char c;
    cin >> m >> p;
    init(200005);
    for (int i = 1; i <= m; ++i) {
        scanf(" %c %d", &c, &t);
        if (c == 'Q')
            a = query(cnt - t, cnt, 0, 0, n), printf("%d\n", a);
        else
            update(cnt++, (t + a) % p);
    }
}