1012: [JSOI2008]最大数maxnumber
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 11990 Solved: 5202
【题目描述】
现在请求你维护一个数列，要求提供以下两种操作：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个数的最大数。
【输入样例】
5 100
A 96
Q 1
A 97
Q 1
Q 2
【输出样例】
96
93
96
HINT
【解题报告】
这题读完其实就知道，其实它是要我们求一个会变化的区间最大值，但这个变化只是延长。
通过我们的经验，求区间最大值常用的就只有几个：
RMQ：但是RMQ只能求固定区间的极值，所以果断排除。
堆：这明显是不可以的。那么我们就会想到线段树，但是也许你会说：“线段树也只能求固定区间的极值。”
其实你可以在建树的时候就先将位置预留下来，就可以了。
还有另一种线段树，不需要建树就可以的，也照样可以解。其实仔细一想，完全可以用单调栈，反正他只是求最后几个，所以完全没问题。
我们建一个单调下降的栈，因为如果当前a[i]>a[j] (i>j)的话，a[j]根本就是无用的，永远也用不上，就像茅坑里的石头，又臭又硬，直接就可以扔掉不用。所以并不需要写麻烦的线段树，单调栈加二分查找轻松OK。
线段树代码：
#include<cstdio>
#include<algorithm>
using namespace std;
struct xcw{int L,R,c;}a[4*200005];
int n,tt,lst=0;
int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') ret=ret*10+ch-48,ch=getchar();
return ret*f;
}
void build(int p,int L,int R){//建树
a[p]=(xcw){L,R,0};
if(L==R) return;
int mid=(R-L>>1)+L;
build(p<<1,L,mid);build((p<<1)+1,mid+1,R);
}
void add(int p,int x,int y){//在x位置上添加y
int L=a[p].L,R=a[p].R;
if(x==L&&x==R){a[p].c=y;return;}
int mid=(R-L>>1)+L;
if(x<=mid) add(p<<1,x,y);else add((p<<1)+1,x,y);
a[p].c=max(a[p<<1].c,a[(p<<1)+1].c);
}
int cnt(int p,int L,int R){//取出L到R之间的最大值
if(a[p].L==L&&a[p].R==R) return a[p].c;
int mid=(a[p].R-a[p].L>>1)+a[p].L;
if(R<=mid) return cnt(p<<1,L,R);else
if(L>mid) return cnt((p<<1)+1,L,R);else return max(cnt(p<<1,L,mid),cnt((p<<1)+1,mid+1,R));
}
int main(){
n=read(),tt=read();
build(1,1,n);
int c=0;
for(int i=1;i<=n;i++){
char ch=getchar();
if(ch=='Q'){
int L=read();
if(!lst) printf("0\n");else//如果没有元素时，肯定是0
if(L>lst) printf("%d\n",c=cnt(1,1,lst));//超过现在的长度时，就是从1开始
else printf("%d\n",c=cnt(1,lst-L+1,lst));
}else{
int y=read();
add(1,++lst,(y+c)%tt);
}
}
return 0;
}单调栈代码：
#include<cstdio>
using namespace std;
int n,tt,tl,que[200005],id[200005],lst,c;
int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') ret=ret*10+ch-48,ch=getchar();
return ret*f;
}
int fnd(int x){//查找x的位置
int L=1,R=tl;
while(L<=R){
int mid=(R-L>>1)+L;
if(id[mid-1]<x&&id[mid]>=x) return que[mid];//如果x在这之间，que[mid]是最大的，因为栈是单调下降的，而mid-1不满足条件。
if(id[mid]>=x) R=mid-1;else L=mid+1;
}
}
int main(){
n=read();tt=read();
for(int i=1;i<=n;i++){
char ch=getchar();
if(ch=='Q'){
int L=read();
if(!lst) printf("0\n");else //栈为空
if(L>lst) printf("%d\n",c=que[1]); //超过当前长度时，就是1号元素
else printf("%d\n",c=fnd(lst-L+1));
}else{
int y=read(),now=(y+c)%tt;
while(que[tl]<now&&tl) tl--; //去除不必要的元素，保证单调下降
que[++tl]=now;id[tl]=++lst;
}
}
return 0;
}
