Submit: 13258 Solved: 5737
[Submit][Status][Discuss]
Description
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是非负整数并且在长整范围内。
注意：初始时数列是空的，没有一个数。
Input
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。
Output
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
93
96
HINT
数据如下http://pan.baidu.com/s/1i4JxCH3
Source
经典线段树
事实证明bzoj永远不要用cin/cout
事实证明bzoj永远不要用cin/cout
事实证明bzoj永远不要用cin/cout
调了我一个小时！！！
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 ?5 const int maxn=800010; 6 ?7 int tree[maxn]; 8 int M,D,t,pos; 9 10 void update(int k,int l,int r,int x)11 {12 ????if(l==r) {tree[k]=x;return;}13 ????int mid=(l+r)>>1;14 ????if(pos<=mid) update(k<<1,l,mid,x);15 ????else update(k<<1|1,mid+1,r,x);16 ????tree[k]=max(tree[k<<1],tree[k<<1|1]);17 }18 19 int search(int k,int l,int r,int s,int t)20 {21 ????if(l==s&&r==t) return tree[k];22 ????int mid=(l+r)>>1;23 ????if(t<=mid) return search(k<<1,l,mid,s,t);24 ????if(s>mid) return search(k<<1|1,mid+1,r,s,t);25 ????return max(search(k<<1,l,mid,s,mid),search(k<<1|1,mid+1,r,mid+1,t));26 }27 28 int main()29 {30 ????scanf("%d%d",&M,&D);31 ????for(int i=1;i<=M;i++)32 ????{33 ????????char o[5];int n;34 ????????scanf("%s",o);35 ????????scanf("%d",&n);36 ????????if(o[0]==‘A‘)37 ????????{38 ????????????pos++;39 ????????????update(1,1,M,(n+t)%D);40 ????????}41 ????????else42 ????????{43 ????????????t=search(1,1,M,pos-n+1,pos);44 ????????????printf("%d\n",t);45 ????????}46 ????}47 ????return 0;48 }1012: [JSOI2008]最大数maxnumber
原文地址：https://www.cnblogs.com/InWILL/p/9175497.html