【题目来源】
【题目描述】
给定一个正整数数列 a1，a2，…，an，每一个数都在 0 ~ p-1 之间。
可以对这列数进行两种操作：
1. 添加操作：向序列后添加一个数，序列长度变成 n+1；
2. 询问操作：询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始，整数序列为空。
一共要对整数序列进行 m 次操作。
写一个程序，读入操作的序列，并输出询问操作的答案。
【输入格式】
第一行有两个正整数 m，p，意义如题目描述；
接下来 m 行，每一行表示一个操作。
如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；
如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。
第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。
【输出格式】
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 L 个数的最大数。
【输入样例】
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≤m≤2×10^5，
1≤p≤2×10^9，
0≤t<p
【算法分析】
● 在常见语境下，RMQ 通常指的是一类问题，即 Range Minimum/Maximum Query（区间最值查询）问题。这类问题要求在给定的数组上，快速回答任意区间内的最小值（或最大值）查询。
RMQ 问题可以分为静态和动态两种情况：
（1）静态 RMQ：数组内容在查询过程中不发生变化，适用于稀疏表（Sparse Table）等预处理算法。
（2）动态 RMQ：数组内容可能发生变化，需要支持动态更新和查询，适用于线段树、树状数组等数据结构。
从算法实现角度来看，RMQ 有多种解决方案，包括稀疏表、线段树、树状数组、动态规划的扩展等，每种算法都有其适用场景和时间复杂度特点。
● 由本题“如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）”的陈述，可知本题数组内容发生变化。所以，本题是动态 RMQ 问题。因此，不能使用静态 RMQ 算法，推荐使用线段树或树状数组等支持动态更新的数据结构。
● 特别要注意，long long 型在本题中的使用。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=2e5+5;
typedef long long LL;
int m,p;struct node {int le,ri;LL mx; //long long
} tr[N*4];void pushup(int u) {tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}void build(int u,int le,int ri) {tr[u]= {le,ri,0};if(le==ri) return;int mid=(le+ri)>>1;build(u<<1,le,mid);build(u<<1|1,mid+1,ri);
}void update(int u,int p,int v) { //Single-point updateif(tr[u].le==p && tr[u].ri==p) tr[u].mx=v;else {int mid=tr[u].le+tr[u].ri>>1;if(p<=mid) update(u<<1,p,v);else update(u<<1|1,p,v);pushup(u);}
}LL query(int u,int le,int ri) {if(tr[u].le>=le && tr[u].ri<=ri) {return tr[u].mx;}int mid=tr[u].le+tr[u].ri>>1;LL v=LLONG_MIN;if(le<=mid) v=query(u<<1,le,ri);if(ri>mid) v=max(v,query(u<<1|1,le,ri));return v;
}int main() {int n=0;LL pre=0; //long longcin>>m>>p;build(1,1,m);char op;int t;while(m--) {cin>>op>>t;if(op=='A') {update(1,n+1,((LL)t+pre)%p);n++;} else {pre=query(1,n-t+1,n);cout<<pre<<endl;}}return 0;
}/*
in:
4 1999999999
A 1999999998
Q 1
A 1999999998
Q 1out:
1999999998
1999999997
*/
【参考文献】