题目描述
现在请求你维护一个数列,要求提供以下两种操作:
1、 查询操作。
语法:Q L
功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。
限制:L不超过当前数列的长度。
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 100 A 96 Q 1 A 97 Q 1 Q 2
输出样例#1:
96 93 96
说明
[JSOI2008]
分析
两个有趣的数组:st单调栈,存数字的下标,数字递减,而下标是递增,num存数字。
操作:如果是A,当前的数字就加入到数组中,维护单调栈,如果Q,在st中搜索大于等于(len-n+1)的数,返回第一个大于等于它的值,然后更新t的值。
为什么这样呢?st数组中村的是数字的下标,这些下标的num值会是单调递减的,越靠前的下标的数字越大,我们搜索大于等于(len-n+1),就是搜索数列中末尾L个数中第(len-n+1)个数,如果栈中找到了的一个数,这就是答案,这个数字满足在末尾L个数中,然后又是最大的,后面的数字都比他小。
code
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int st[200100],num[200100]; //st单调栈,递减,存下标,num存数字 6 char s[5]; 7 8 int main() 9 { 10 int n,m,d,len = 0,siz = 0,t = 0; 11 scanf("%d%d",&m,&d); 12 while (m--) 13 { 14 scanf("%s%d",s,&n); 15 if (s[0]=='A') 16 { 17 n = (n+t)%d; 18 num[++len] = n; 19 while (siz&&num[st[siz]]<=n) siz--; 20 st[++siz] = len; 21 } 22 else 23 { 24 int tmp = lower_bound(st+1,st+siz+1,len-n+1)-st; 25 t = num[st[tmp]]; 26 printf("%d ",t); 27 } 28 } 29 return 0; 30 }