https://www.luogu.org/problemnew/show/P1198

现在请求你维护一个数列，要求提供以下两种操作：

1、 查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：LL不超过当前数列的长度。(L > 0)(L>0)

2、 插入操作。

语法：A n

功能：将nn加上tt，其中tt是最近一次查询操作的答案（如果还未执行过查询操作，则t=0t=0)，并将所得结果对一个固定的常数DD取模，将所得答案插入到数列的末尾。

限制：nn是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入格式：

第一行两个整数，MM和DD，其中MM表示操作的个数(M \le 200,000)(M≤200,000)，DD如上文中所述，满足(0<D<2,000,000,000)(0<D<2,000,000,000)

接下来的MM行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式：

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入样例#1： 复制

5 100
A 96
Q 1
A 97
Q 1
Q 2

输出样例#1： 复制

96
93
96

单调栈解法。因为题目求的是末尾L个数的最大值，利用两个栈分别存储最大值和最大值的位置。然后二分查找。注意二分查找时上界是总得个数减去区间长度，而不是栈的空间减去区间长度，因为不符合栈的数值已经出栈了。

单调栈解法参考自：https://www.luogu.org/blog/user38348/solution-p1198

#include
#include
#include
#define ll long long
using namespace std;
long long Stack[2][200010];
long long cnt=0,top=0;
void add(long long val){
cnt++;
while(Stack[0][top]0)) top--;
Stack[0][++top]=val;
Stack[1][top]=cnt;
}
long long quiry(long long L){
int l=1,r=top;
int ind=cnt-L+1;
// int ind=top-L+1;
while(l>1;
if(Stack[1][mid]>c>>d;
if(c=='A'){
add((t+d)%D);
}
else if(c=='Q'){
t=quiry(d);
printf("%lld\n",t);
}
}
return 0;
}

线段树解法，维护区间的最大值。

#include
#include
#include
#define ll long long
using namespace std;
const int maxn=200010*4;
ll Max[maxn];

void add(int p,int l,int r,int x,ll c){
if(l==r){
Max[p]=c;return;
}
int mid=(l+r)>>1;
if(x<=mid) add(p<<1,l,mid,x,c); else add(p<<1|1,mid+1,r,x,c); Max[p]=max(Max[p<<1],Max[p<<1|1]); } int quiry(int p,int l,int r,int a,int b){ if(a>r||b>1;
return max(quiry(p<<1,l,mid,a,b),quiry(p<<1|1,mid+1,r,a,b)); } int main(int argc, char** argv) { int M,D; scanf("%d %d",&M,&D); fill(Max,Max+maxn,-1e8); ll t=0; int x=0; while(M--){ char c;int d; cin>>c>>d;
if(c=='A'){
x++;
ll num=(t+d)%D;
add(1,1,200010,x,num);
}else if(c=='Q'){
t=quiry(1,1,200010,x-d+1,x);
printf("%lld\n",t);
}
}
return 0;
}