★★   输入文件：bzoj_1012.in   输出文件：bzoj_1012.out   简单对比
时间限制：3 s   内存限制：162 MB

【题目描述】

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

【输入格式】

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足1≤int64max

【输出格式】

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

【样例输入】

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

【样例输出】

96
93
96

【题目来源】

耒阳大视野（衡阳八中） OJ 1012

方法一 线段树 单点修改 RMQ

方法二 维护一个单调栈

屠龙宝刀点击就送

#include
#define Max 200000

typedef long long LL;
struct node
{
LL Maxn,l,r,dis;
}tr[Max<<]; LL M,D,pos=,t=; LL max(LL a,LL b) { return a>b?a:b;
}
void up(LL k)
{
tr[k].Maxn=max(tr[k<<].Maxn,tr[k<<|].Maxn); } void build(LL k,LL l,LL r) { tr[k].l=l; tr[k].r=r; if(l==r) { tr[k].dis=;tr[k].Maxn=; return; } LL mid=(l+r)>>;
build(k<<,l,mid); build(k<<|,mid+,r); up(k); } void add(LL k,LL t,LL v) { if(tr[k].l==tr[k].r) { tr[k].dis+=v; tr[k].Maxn=tr[k].dis; return; } LL mid=(tr[k].l+tr[k].r)>>;
if(mid>=t) add(k<<,t,v); else add(k<<|,t,v); up(k); } LL query(LL k,LL l,LL r) { if(tr[k].l==l&&tr[k].r==r) return tr[k].Maxn; LL mid=(tr[k].l+tr[k].r)>>;
if(l>mid) return query(k<<|,l,r);
else if(r<=mid) return query(k<<,l,r);
else return max(query(k<<,l,mid),query(k<<|,mid+,r));
}
int main()
{
scanf("%lld%lld",&M,&D);
build(,,M);
char str[];
for(LL x;M--;)
{
scanf("%s",str+);
switch(str[])
{
case 'A':
{
scanf("%lld",&x);
add(,++pos,(x+t)%D);
break;
}
case 'Q':
{
scanf("%lld",&x);
t=query(,pos-x+,pos);
printf("%lld\n",t);
break;
}
}
}
return ;
}

线段树

#include
using namespace std;
#define N 200005
typedef long long LL;

void read(LL &x)
{
x=;bool f=;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=;
ch=getchar();
}
while(isdigit(ch))
{
x=x*+ch-'';
ch=getchar();
}
x=f?(~x)+:x;
}
LL Num[N],s[N],top,cnt,a[N],M,D,t=;
int main()
{
read(M);
read(D);
char str[];
for(LL x;M--;)
{
scanf("%s",str+);
switch(str[])
{
case 'A':
{
scanf("%lld",&x);
LL y=(x+t)%D;
a[++cnt]=y;
while(top&&a[s[top]]<=y) top--; s[++top]=cnt; break; } case 'Q': { scanf("%lld",&x); int l=,r=top; while(l>;
if(s[mid]<cnt-x+) l=mid+;
else r=mid;
}
int y=l;
t=a[s[l]];
printf("%lld\n",a[s[y]]);
break;
}
}
}
return ;
}

单调栈