<—点个赞吧QwQ

宣传一下算法提高课整理

给定一个正整数数列 $a_1,a_2,…,a_n$，每一个数都在 $0 \sim p-1$ 之间。

可以对这列数进行两种操作：

1. 添加操作：向序列后添加一个数，序列长度变成 $n+1$；
2. 询问操作：询问这个序列中最后 $L$ 个数中最大的数是多少。

程序运行的最开始，整数序列为空。

一共要对整数序列进行 $m$ 次操作。

写一个程序，读入操作的序列，并输出询问操作的答案。

输入格式

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

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

如果该行的内容是 Q L，则表示这个操作是询问序列中最后 $L$ 个数的最大数是多少；

如果是 A t，则表示向序列后面加一个数，加入的数是 $(t+a)\ bmod\ p$。其中，$t$ 是输入的参数，$a$ 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 $a=0$）。

第一个操作一定是添加操作。对于询问操作，$L>0$ 且不超过当前序列的长度。

输出格式

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 $L$ 个数的最大数。

数据范围

$1 \le m \le 2 \times 10^5$,
$1 \le p \le 2 \times 10^9$,
$0 \le t < p$

输入样例：

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

样例解释

最后的序列是 $97,14,60,96$。

思路

如果不懂线段树就看线段树详解（超详细）
这题就是维护一个最大值，这里最多有 $m$ 个操作，所以数组最多有 $m$ 个数，每次加一个数，我们把线段树的查询区间改一下即可。

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200010;
int n = 0,m,p;
LL last = 0;
struct {
    int l,r;
    LL v;
}c[4*N];
void pushup (int u) {
    c[u].v = max (c[u*2].v,c[u*2+1].v);
}
void build (int u,int l,int r) {
    c[u] = {l,r};
    if (l == r) return ;
    int mid = l+r >> 1;
    build (u*2,l,mid),build (u*2+1,mid+1,r);
}
void fix (int u,int x,int v) {
    if (c[u].l == x && c[u].r == x) c[u].v = v;
    else {
        int mid = c[u].l+c[u].r >> 1;
        if (x <= mid) fix (u*2,x,v);
        else fix (u*2+1,x,v);
        pushup (u);
    }
}
LL query (int u,int l,int r) {
    if (c[u].l >= l && c[u].r <= r) return c[u].v;
    int mid = c[u].l+c[u].r >> 1;
    LL ans = 0;
    if (l <= mid) ans = max (ans,query (u*2,l,r));
    if (r > mid) ans = max (ans,query (u*2+1,l,r));
    return ans;
}
int main () {
    cin >> m >> p;
    build (1,1,m);
    while (m--) {
        char ch;
        int x;
        cin >> ch >> x;
        if (ch == 'A') fix (1,++n,(last+x)%p);
        else {
            last = query (1,n-x+1,n);
            cout << last << endl;
        }
    }
    return 0;
}