最大数
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入输出格式
输入格式：
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入样例：
5 100
A 96
Q 1
A 97
Q 1
Q 2
输出样例：
96
93
96
标签：线段树
线段树裸题。
记录当前长度$len$，每个结点维护区间最大值，操作1为$query(len-L+1, len)$，操作2为$modify(++len, (n+t)%D)$。
注意开longlong
附上AC代码：
#include <iostream>
#include <cstdio>
#define MAX_N 200000
#define INF 2000000000
#define ll long long
using namespace std;
ll tree[MAX_N*4+50];
int n, len = 0;
void updata(int v) {
tree[v] = max(tree[v<<1], tree[v<<1|1]);
}
void build(int v, int s, int t) {
if (s == t) {
tree[v] = -INF;
return;
}
int mid = s+t>>1;
build(v<<1, s, mid);
build(v<<1|1, mid+1, t);
updata(v);
}
void modify(int v, int s, int t, int pos, ll x) {
if (s == t) {
tree[v] = x;
return;
}
int mid = s+t>>1;
if (pos <= mid) {
modify(v<<1, s, mid, pos, x);
} else {
modify(v<<1|1, mid+1, t, pos, x);
}
updata(v);
}
ll query(int v, int s, int t, int l, int r) {
if (s >= l && t <= r) {
return tree[v];
}
int mid = s+t>>1;
ll ret = -INF;
if (l <= mid) {
ret = max(ret, query(v<<1, s, mid, l, r));
}
if (r >= mid+1) {
ret = max(ret, query(v<<1|1, mid+1, t, l, r));
}
return ret;
}
int main() {
ll x, prev = 0, mod;
char opt;
int l;
scanf("%d%lld", &n, &mod);
build(1, 1, n);
for (int i = 0; i < n; i++) {
cin >> opt;
if (opt == 'A') {
scanf("%lld", &x);
modify(1, 1, n, ++len, (x%mod+prev)%mod);
} else {
scanf("%d", &l);
prev = query(1, 1, n, len-l+1, len);
printf("%lld
", prev);
prev %= mod;
}
}
return 0;
}