题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。(L>=0)
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入输出格式
输入格式：
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入样例#1：
5 100A 96Q 1A 97Q 1Q 2
输出样例#1： View Code
969396
做这道题的时候，在洛谷上交一直T,不知道为什么，后来把读优换成cin就过了，我就想呵呵了。
题解：
裸的线段树。直接说做法吧。还有一件十分重要的事，记得开Long Long。
ε=(′ο｀*)))唉。
先建一棵1-m的线段树。
在进行操作的时候，维护当前序列长度。
那么加数是,len++,进行单点修改。
询问时，相当于询问区间[len-i+1,len]的最大值。
搞定。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #define ll long long 9 #define DB double10 #define mod 100000000711 using namespace std;12 inline ll read()13 {14 ????ll x=0,w=1;char ch=getchar();15 ????while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘) w=-1;ch=getchar();}16 ????while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();17 ????return x*w;18 }19 const ll N=200010,n=200000;20 const ll inf=1ll<<60;21 ll t[N*5],m,D,k,len;22 void build(ll o,ll l,ll r)23 {24 ????if(l==r)25 ????{26 ????????t[o]=-inf;27 ????????return;28 ????}29 ????ll mid=(l+r)>>1;30 ????build(o<<1,l,mid);build(o<<1|1,mid+1,r);31 ????t[o]=max(t[o<<1],t[o<<1|1]);32 }33 void update(ll o,ll l,ll r,ll x,ll p)34 {35 ????if(x>=l && x<=r) t[o]=max(t[o],p);36 ????else return;37 ????if(l==r)return;38 ????ll mid=(l+r)>>1;39 ????update(o<<1,l,mid,x,p);40 ????update(o<<1|1,mid+1,r,x,p);41 }42 ll query(ll o,ll l,ll r,ll x,ll y)43 {44 ????if(x<=l && y>=r) return t[o];45 ????ll mid=(l+r)>>1,ans=-inf;46 ????if(x<=mid) ?ans=max(ans,query(o<<1,l,mid,x,y));47 ????if(y>=mid+1) ans=max(ans,query(o<<1|1,mid+1,r,x,y));48 ????return ans;49 }50 int main()51 {52 ????m=read();D=read();53 ????build(1,1,n);54 ????while(m--)55 ????{56 ????????char s[4];scanf("%s",s);57 ????????ll x;x=read();58 ????????if(s[0]==‘A‘)59 ????????{60 ????????????x=(x+k)%D;61 ????????????len++;update(1,1,n,len,x);62 ????????}else{63 ????????????if(x==0){printf("0\n");continue;}64 ????????????k=query(1,1,n,len-x+1,len);65 ????????????printf("%lld\n",k);66 ????????}67 ????}68 ????return 0;69 }居卑而后知登高之为危，处晦而后知向明之太霭。
[JSOI2008]最大数
原文地址：https://www.cnblogs.com/adelalove/p/8485864.html