题目：
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
线段树版
思路：
先把树开满，没出现的数都设成零，单点修改，区间查询。
代码：
#include <iostream>#include <cstdio>using namespace std;typedef unsigned long long ull;ull tree[524288],dep;int firstbit(int n){int ans=0; ???n--; ???while(n){ ???????ans++; ???????n>>=1; ???} ???return 1<<ans;}void update(int w,int n){ ???w+=dep; ???tree[w]+=n; ???for(w>>=1;w;w>>=1) ???????tree[w]=max(tree[w<<1],tree[w<<1|1]);}ull query(int l,int r){ull ans=0; ???for(int lc=l+dep-1,rc=r+dep+1;lc^rc^1;lc>>=1,rc>>=1){ ???????if(~lc&1) ???????????ans=max(ans,tree[lc^1]); ???????if( rc&1) ???????????ans=max(ans,tree[rc^1]); ???} ???return ans;}int main(){int t=0,w=1,M,D; ???ios::sync_with_stdio(false); ???cin>>M>>D; ???dep=firstbit(200005); ???while(M--){ ???????char c; ???????cin>>c; ???????if(c==‘A‘){ ???????????int n; ???????????cin>>n; ???????????update(w,(t+n)%D); ???????????w++; ???????} ???????else{ ???????????int n; ???????????cin>>n; ???????????t=query(w-n,w-1)%D; ???????????cout<<t<<endl; ???????} ???} ???return 0;}
单调栈版
思路：
用单调栈维护最大值，在栈中二分查找答案。
代码：
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;typedef unsigned long long ull;struct Node{int no;ull n;};bool cmp(Node a,Node b){return a.no<b.no;}Node s[200005];int main(){int t=0,top=-1,D,M,w=1;ios::sync_with_stdio(false);cin>>M>>D;while(M--){char c;cin>>c;if(c==‘A‘){int tem,n;cin>>n;tem=(t+n)%D;while(~top&&s[top].n<tem)top--;top++;s[top].n=tem;s[top].no=w++;}else {int whe;Node n;cin>>n.no;n.no=w-n.no;whe=lower_bound(s,s+top+1,n,cmp)-s;t=s[whe].n;cout<<t<<endl;}}return 0;}
JSOI2008 最大数
原文地址：http://www.cnblogs.com/HC-LittleJian/p/7753353.html