首页 > 代码库 > 最大数
最大数
现在请求你维护一个数列,要求提供以下两种操作:
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]
维护一个单调站,二分查找序号。唔,看的题解
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<math.h> #include<queue> #include<vector> #include <cmath> using namespace std; int a[210000],b[210000],p,n,k,x,y; long long d; int find(int l,int r,int o) { int m=(l+r)>>1; while(l!=r) { if(b[m]<o) l=m+1; if(b[m]>o) r=m; if(b[m]==o) return m; m=(r+l)>>1; } return m; } int main() { scanf("%d%lld",&n,&d); char c; for(int i=1;i<=n;i++) { cin>>c;scanf("%d",&y); if(c==‘A‘) { k++; y=(x+y)%d; a[k]=y; while(p>0&&a[b[p]]<=y) p--; p++; b[p]=k; } if(c==‘Q‘) { x=a[b[find(1,p,k-y+1)]]; printf("%d\n",x); } } }
最大数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。