Description
现在请求你维护一个数列,要求提供以下两种操作: 1、 查询操作。语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。 2、 插入操作。语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个数。
Input
第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足(0
Output
对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。
Sample Input
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
93
96
HINT
维护一棵线段树。。。插入点和查询时处理一下即可。
Source:
#include <iostream>
#include <cstdio>
#define N 200000
using namespace std;
int segtree[*N];
int n,me,ans;
void adddata(int now)
{
segtree[now]=max(segtree[(now<<)],segtree[(now<<)+]);
}
void pointchange(int now,int l,int r,int x,int v)
{
if (l==r) {segtree[now]+=v; segtree[now]%=me; return;}
int mid=(l+r)>>;
if (x<=mid) pointchange((now<<),l,mid,x,v);
else pointchange((now<<)+,mid+,r,x,v);
adddata(now);
}
void query(int now,int l,int r,int begin,int end)
{
if (begin<=l && end>=r) {ans=max(ans,segtree[now]);return;}
int mid=(l+r)>>;
if (begin<=mid) query((now<<),l,mid,begin,end);
if (end>mid) query((now<<)+,mid+,r,begin,end);
}
int main()
{
int i,num=,x;
char s[];
scanf("%d%d",&n,&me);
for (i=;i<=n;i++)
{
scanf("%s %d",s,&x);
if (s[]=='A')
{
num++;
pointchange(,,n,num,ans+x);
}
else
{
ans=-;
query(,,n,num-x+,num);
printf("%d\n",ans);
}
}
return ;
}
【BZOJ1012】 【JSOI2008】最大数maxnumber的更多相关文章
-
BZOJ1012: [JSOI2008]最大数maxnumber [线段树 | 单调栈+二分]
1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 8748 Solved: 3835[Submi ...
-
BZOJ-1012[JSOI2008]最大数maxnumber 线段树区间最值
这道题相对简单下面是题目: 1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec Memory Limit: 162 MB Submit: 6542 Solve ...
-
bzoj1012: [JSOI2008]最大数maxnumber(貌似是道线段树喔)
1012: [JSOI2008]最大数maxnumber 题目:传送门 题解: 发现自己空了一道水题... 1~210000建线段树,其实就是一道裸题... 单点修改+区间查询...1A~ 代码: # ...
-
BZOJ1012 [JSOI2008]最大数maxnumber
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...
-
bzoj1012: [JSOI2008]最大数maxnumber [单调队列]
Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插 ...
-
[BZOJ1012] [JSOI2008] 最大数maxnumber (ST表)
Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插 ...
-
BZOJ1012:[JSOI2008]最大数maxnumber(线段树)
Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L 个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. ...
-
【听说是线段树】bzoj1012 [JSOI2008]最大数maxnumber
一眼看题目吓了一跳:这TM不就是单调队列吗,200000又怎样,大不了我二分嘛 系统提示:成功开启 手残模式 开始瞎写: #include <cstdio> ]; ]; int m,mod ...
-
BZOJ1012——[JSOI2008]最大数maxnumber
1.题目大意:求末尾L个数的最大值,强制在线 2.分析:这个拿线段树可以直接水过,然后我写了一个 维护单调栈, 二分求最大值的短代码,手懒.... #include <cstdio> #i ...
-
BZOJ1012[JSOI2008]最大数maxnumber 题解
题目大意: 维护一个数列,有两种操作:1. 查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2.插入操作:将n加上t,其中t是最近一次查询操作的答案(如果还未执行 ...
随机推荐
-
【Django】--Model字段
参考地址:http://www.cnblogs.com/wupeiqi/articles/6216618.html 所有字段 AutoField(Field) --int自增列,必须填入参数prima ...
-
java-collections.sort异常Comparison method violates its general contract!
转载:http://www.tuicool.com/articles/MZreyuv 异常信息 java.lang.IllegalArgumentException: Comparison metho ...
-
教你把UltraEdit如何注册激活教程及UltraEdit 22.0.0.48 官方中文版下载
UltraEdit 22.0.0.48 官方中文版下载:链接: http://pan.baidu.com/s/1i3f7mZV 密码: r23v2015-5-30号更新 第一.关闭网络连接(或者直接拔 ...
-
FZU 2214 Knapsack dp (转化背包)
就是一个背包裸题,由于物品的重量太大,开不了这么大的数组 所以转化一下,由于价值总和不大于5000,所以把价值看作重量,重量看作价值,那么就是同样的价值下,求一个最轻的重量 #include<c ...
-
poj2578---三个数中找出第一个大于168的
#include <stdio.h> #include <stdlib.h> int main() { int a,b,c; scanf("%d %d %d" ...
-
RedHat 7 常用命令总结
Linux RedHat 7常用命令总结... ----------------------- 征服Linux从终端开始 ------------------------------------- 在 ...
-
JBOSS EAP6 系列二 客户端访问位于EAR中的EJB时,jndi name要遵守的规则
EJB 的 jndi语法(在整个调用远程ejb的过程中语法的遵循是相当重要的) 参见jboss-as-quickstarts-7.1.1.CR2\ejb-remote\client\src\main\ ...
-
(5)Linux权限管理
1.文件权限 2.1)文件类型 d:目录 -:文件 l:链接文件 b:可以存储的接口设备 c:串行端口设备(键盘,鼠标) 2)文件属性 接下来的九个字符以三个为一组分别是 rw ...
-
Linux 基本操作--文件查看 (day3)
一.查看文件-----cat (详情参考:http://blog.sina.com.cn/s/blog_52f6ead0010127xm.html) 语法结构: cat 查看方式 文件 cat -A ...
-
Unity热更新学习(二) —— ToLua c#与lua的相互调用
tolua 下载地址:http://www.ulua.org/index.html c#调用lua的方法,tolua的官方例子提供了很多种.我初步学了一种在做项目使用的方法.通过DoFile方法执行l ...