Problem 现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加 上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取 模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个 数。
Input 第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来 M行，查询操作或者插入操作。
Output 对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。
Sample Input Sample Output 5 100 A 96 Q 1 A 97 Q 1 Q 2 96 93 96
题解：简单的线段树模板题，建一颗空树逐个更新最大值就可以了，或者直接储存一个后缀里面最大数，每次更新，加上break，复杂度在不卡数据的时候还可以。
1、线段树
代码语言：javascript复制#include <iostream>
#include <bits/stdc .h>
using namespace std;
const int MAX = 200000;
struct node
{
int l, r;
int w;
};
struct node tree[MAX *4 10];
int a[MAX] = {0};
int ans = 0;
void BuildTree(int l, int r, int k)
{
tree[k].l = l;
tree[k].r = r;
if(l == r)
{
tree[k].w = a[l];
return ;
}
int m = (tree[k].l tree[k].r) >> 1;
BuildTree(l, m,k << 1);
BuildTree(m 1, r, k << 1 | 1);
tree[k].w = max(tree[k << 1].w, tree[k << 1 | 1].w);
}
void SingleModify(int k, int x, int y)
{
if(tree[k].l == x && tree[k].r == x)
{
tree[k].w = y;
return ;
}
int m = (tree[k].l tree[k].r) / 2;
if(x <= m) SingleModify(k<<1,x,y);
else SingleModify(k<<1|1,x,y);
tree[k].w = max(tree[k<<1].w, tree[k<<1|1].w);
}
void IntervalQuery(int k, int x, int y)
{
if(tree[k].l >= x && tree[k].r <= y)
{
ans = max(ans,tree[k].w);
return ;
}
int m = (tree[k].l tree[k].r) >>1;
if(x <= m) IntervalQuery(k<<1,x,y);
if(y > m) IntervalQuery(k <<1 |1,x, y);
}
char op;
int main()
{
int M, D, t, L, n, x, top;
while(~scanf("%d %d",&M, &D))
{
BuildTree(1,MAX,1);
t = 0;
top = 0;
while(M --)
{
getchar();
scanf("%c %d",&op, &x);
if(op == 'A')
{
n = x;
n = (n t) % D;
SingleModify(1,top 1,n);
top ;
}
else
{
L = x;
ans = 0;
IntervalQuery(1,top - L 1, top);
t = ans;
printf("%dn",ans);
}
}
}
return 0;
}2、优雅的暴力（复杂度在最坏情况下会TLE，不过不卡数据还可以）
代码语言：javascript复制#include <iostream>
#include <bits/stdc .h>
using namespace std;
typedef long long ll;
const int N = 2e5 10;
ll a[N]; // 储存所有数据
ll b[N]; // 存储后缀的最大值，b[i]表示后i个数的最大值
int main()
{
ll m,mod,n,x,y,i,j,k,f; // x是查询后保留值
char op;
while(~scanf("%lld %lld", &m, &mod))
{
i = 1; j = 1; k = 0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
x = 0; f = 0;
for(ll p = 1; p <= m; p )
{
getchar();
scanf("%c %lld", &op, &n);
if(op == 'A')
{
if(f == 0) // 一直是添加的情况，当前没有查询，一旦查询之后就需要Mod
{
y = n % mod;
a[i ] = y;
b[j ] = y;
if(a[i - 1] <= a[i - 2]); //如果新添加的这个数比倒数第二个小，不需要更新
else
{
for(k = i - 2; k >= 0; k --) // 从后面开始更新
{
if(y > b[k])b[k] = y;
else break;
}
}
}
else
{
y = (n x) % mod;
a[i ] = y;
b[j ] = y;
if(a[i - 1] <= a[i - 2]);
else
{
for(k = i - 2; k >= 0; k --)
{
if(y > b[k])b[k] = y;
else break;
}
}
}
}
else if(op == 'Q') // 访问情况， 保留x
{
f = 1;
x = b[j - n];
printf("%lldn",x);
}
}
}
return 0;
}
