【BZOJ1012】 【JSOI2008】最大数maxnumber

时间:2022-09-03 10:49:15

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

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
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的更多相关文章

  1. BZOJ1012&colon; &lbrack;JSOI2008&rsqb;最大数maxnumber &lbrack;线段树 &vert; 单调栈&plus;二分&rsqb;

    1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 8748  Solved: 3835[Submi ...

  2. BZOJ-1012&lbrack;JSOI2008&rsqb;最大数maxnumber 线段树区间最值

    这道题相对简单下面是题目: 1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec Memory Limit: 162 MB Submit: 6542 Solve ...

  3. bzoj1012&colon; &lbrack;JSOI2008&rsqb;最大数maxnumber&lpar;貌似是道线段树喔&rpar;

    1012: [JSOI2008]最大数maxnumber 题目:传送门 题解: 发现自己空了一道水题... 1~210000建线段树,其实就是一道裸题... 单点修改+区间查询...1A~ 代码: # ...

  4. BZOJ1012 &lbrack;JSOI2008&rsqb;最大数maxnumber

    本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...

  5. bzoj1012&colon; &lbrack;JSOI2008&rsqb;最大数maxnumber &lbrack;单调队列&rsqb;

    Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插 ...

  6. &lbrack;BZOJ1012&rsqb; &lbrack;JSOI2008&rsqb; 最大数maxnumber &lpar;ST表&rpar;

    Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插 ...

  7. BZOJ1012&colon;&lbrack;JSOI2008&rsqb;最大数maxnumber&lpar;线段树&rpar;

    Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L 个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. ...

  8. 【听说是线段树】bzoj1012 &lbrack;JSOI2008&rsqb;最大数maxnumber

    一眼看题目吓了一跳:这TM不就是单调队列吗,200000又怎样,大不了我二分嘛 系统提示:成功开启 手残模式 开始瞎写: #include <cstdio> ]; ]; int m,mod ...

  9. BZOJ1012——&lbrack;JSOI2008&rsqb;最大数maxnumber

    1.题目大意:求末尾L个数的最大值,强制在线 2.分析:这个拿线段树可以直接水过,然后我写了一个 维护单调栈, 二分求最大值的短代码,手懒.... #include <cstdio> #i ...

  10. BZOJ1012&lbrack;JSOI2008&rsqb;最大数maxnumber 题解

    题目大意: 维护一个数列,有两种操作:1. 查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2.插入操作:将n加上t,其中t是最近一次查询操作的答案(如果还未执行 ...

随机推荐

  1. 【Django】--Model字段

    参考地址:http://www.cnblogs.com/wupeiqi/articles/6216618.html 所有字段 AutoField(Field) --int自增列,必须填入参数prima ...

  2. java-collections&period;sort异常Comparison method violates its general contract&excl;

    转载:http://www.tuicool.com/articles/MZreyuv 异常信息 java.lang.IllegalArgumentException: Comparison metho ...

  3. 教你把UltraEdit如何注册激活教程及UltraEdit 22&period;0&period;0&period;48 官方中文版下载

    UltraEdit 22.0.0.48 官方中文版下载:链接: http://pan.baidu.com/s/1i3f7mZV 密码: r23v2015-5-30号更新 第一.关闭网络连接(或者直接拔 ...

  4. FZU 2214 Knapsack dp &lpar;转化背包&rpar;

    就是一个背包裸题,由于物品的重量太大,开不了这么大的数组 所以转化一下,由于价值总和不大于5000,所以把价值看作重量,重量看作价值,那么就是同样的价值下,求一个最轻的重量 #include<c ...

  5. poj2578---三个数中找出第一个大于168的

    #include <stdio.h> #include <stdlib.h> int main() { int a,b,c; scanf("%d %d %d&quot ...

  6. RedHat 7 常用命令总结

    Linux RedHat 7常用命令总结... ----------------------- 征服Linux从终端开始 ------------------------------------- 在 ...

  7. JBOSS EAP6 系列二 客户端访问位于EAR中的EJB时,jndi name要遵守的规则

    EJB 的 jndi语法(在整个调用远程ejb的过程中语法的遵循是相当重要的) 参见jboss-as-quickstarts-7.1.1.CR2\ejb-remote\client\src\main\ ...

  8. (5)Linux权限管理

    1.文件权限 2.1)文件类型 d:目录    -:文件    l:链接文件    b:可以存储的接口设备    c:串行端口设备(键盘,鼠标) 2)文件属性 接下来的九个字符以三个为一组分别是 rw ...

  9. Linux 基本操作--文件查看 (day3&rpar;

    一.查看文件-----cat (详情参考:http://blog.sina.com.cn/s/blog_52f6ead0010127xm.html) 语法结构: cat 查看方式 文件 cat  -A ...

  10. Unity热更新学习(二) —— ToLua c&num;与lua的相互调用

    tolua 下载地址:http://www.ulua.org/index.html c#调用lua的方法,tolua的官方例子提供了很多种.我初步学了一种在做项目使用的方法.通过DoFile方法执行l ...