Description
现在请求你维护一个数列，要求提供以下两种操作： 1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。
Input
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0
Output
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2Sample Output
96
93
96题目分析：
线段树 极限是200000次操作都插入数字 那么就留出辣么大空间就好了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long d;
struct your
{
int x,y;
long long maxx;
}a[1000000];
char s[2];
int len;
void build(int dx,int dy,int num)
{
a[num].x=dx,a[num].y=dy;
if(a[num].x==a[num].y)
return ;
int mid=(dx+dy)>>1;
build(dx,mid,num<<1);
build(mid+1,dy,num<<1|1);
}
long long t;
void update(int x,long long c,int num)
{
if(a[num].x==a[num].y&&a[num].x==x)
{
a[num].maxx=c;
return ;
}
int mid=(a[num].x+a[num].y)>>1;
if(x>mid) update(x,c,num<<1|1);
else update(x,c,num<<1);
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
}
long long ask(int dx,int dy,int num)
{
if(a[num].x==dx&&a[num].y==dy)
return a[num].maxx;
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) return ask(dx,dy,num<<1|1);
else if(dy<=mid) return ask(dx,dy,num<<1);
else
return max(ask(dx,mid,num<<1),ask(mid+1,dy,num<<1|1));
}
int main()
{
scanf("%d%lld",&n,&d);
build(1,200000,1);
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%s%d",&s[0],&tmp);
if(s[0]=='A')
update(++len,(t+tmp)%d,1);
else if(s[0]=='Q')
{
t=ask(len-tmp+1,len,1);
printf("%lld\n",t);
}
}
return 0;
}
