BZOJ 1012: [JSOI2008]最大数maxnumber【线段树单点更新求最值，单调队列，多解】

现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
#define inf 0x7fffffff
inline int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>)
write(x/);
putchar(x%+'');
}
struct Tree
{
int L,R,maxn;
}tree[N<<];
inline void buildtree(int l,int r,int pos)
{
tree[pos].L=l;
tree[pos].R=r;
tree[pos].maxn=-inf;
if(l==r)
return;
int mid=(l+r)/;
buildtree(l,mid,pos*);
buildtree(mid+,r,pos*+);
}
inline int Query(int l,int r,int pos)
{
if(tree[pos].L==l&&tree[pos].R==r)
return tree[pos].maxn;
int mid=(tree[pos].L+tree[pos].R)/;
if(r<=mid)
return Query(l,r,pos*);
else if(l>mid)
return Query(l,r,pos*+);
else return max(Query(l,mid,pos*),Query(mid+,r,pos*+));
}
inline void update(int l,int r,int pos)
{
if(tree[pos].L==tree[pos].R)
{
tree[pos].maxn=r;
return;
}
int mid=(tree[pos].L+tree[pos].R)/;
if(l<=mid)
update(l,r,pos*);
else update(l,r,pos*+);
tree[pos].maxn=max(tree[pos*].maxn,tree[pos*+].maxn);
}
int m,mod,last,cnt;
int main()
{
m=read();
mod=read();
buildtree(,m,);
for(int i=;i<=m;i++)
{
char ch[];
scanf("%s",ch);
int x;
if(ch[]=='A')
{
cnt++;
x=read();
x=(x+last)%mod;
update(cnt,x,);
}
else
{
x=read();
last=Query(cnt-x+,cnt,);
printf("%d\n",last);
}
}
return ;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn=;
int m,d,a[maxn<<],t,maxx[maxn<<],l,p;
char q[];
int main()
{
scanf("%d%d",&m,&d);
while(m--)
{
scanf("%s%d",q,&p);
if(q[]=='A')
{
a[++t]=(l+p)%d;
for(int i=t;i;i--)
{
if(maxx[i]<a[t])
maxx[i]=a[t];
else break;
}
}
else printf("%d\n",l=maxx[t-p+]);
}
return ;
}