单调栈 BZOJ1012 [JSOI2008]最大数maxnumber

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 10440  Solved: 4571
[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

Sample Output

96

93

96

HINT

  数据如下http://pan.baidu.com/s/1i4JxCH3

很容易发现题目要求维护的是单调栈……

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,d,t,x;
 7 char ch,hh;
 8 int top,len,pos[200010],num[200010];
 9 int main(){
10     scanf("%d%d",&n,&d);
11     while(n--){
12         scanf("%c%c%c%d",&hh,&ch,&hh,&x);
13         if(ch==‘A‘){
14             x=(x+t)%d;
15             num[++len]=x;
16             while(top&&num[pos[top]]<=x) top--;
17             pos[++top]=len;
18         }
19         else{
20             int tmp=lower_bound(pos+1,pos+top+1,len-x+1)-pos;
21                 t=num[pos[tmp]];
22                 printf("%d\n",t);
23         }
24     }
25     return 0;
26 }
时间: 07-14

单调栈 BZOJ1012 [JSOI2008]最大数maxnumber的相关文章

BZOJ1012 JSOI2008 最大数maxnumber 线段树/栈+二分法

题意:给定一个数列,要求维护:1.求倒数L个数中的最大值  2.在数列末尾插入(最近的1询问的答案+x)%D.其中初始序列为空. 法一:因为询问最多200000个,所以直接建一棵大小为M的线段树维护即可 #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; struc

[BZOJ1012] [JSOI2008] 最大数maxnumber (ST表)

Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插入操作.语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾.限制:n是非负整数并且在长整范围内.注意:初始时数列是空的,没有一个数. Input 第一行两个整数,M和D,其中M表示操作的个

bzoj1012 [JSOI2008]最大数maxnumber

这道题有很多的做法 裸的线段树 #include<cstdio> #define lc o*2 #define rc o*2+1 #define mid (l+r)/2 inline int max(int x,int y){ return x>y? x:y; } inline int read(){ char c; while(c=getchar(),c<'0' || c>'9'); int x=c-'0'; while(c=getchar(),c>='0' &

bzoj1012: [JSOI2008]最大数maxnumber [单调队列]

Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插入操作.语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾.限制:n是非负整数并且在长整范围内.注意:初始时数列是空的,没有一个数. Input 第一行两个整数,M和D,其中M表示操作的个

【听说是线段树】bzoj1012 [JSOI2008]最大数maxnumber

一眼看题目吓了一跳:这TM不就是单调队列吗,200000又怎样,大不了我二分嘛 系统提示:成功开启 手残模式 开始瞎写: 1 #include <cstdio> 2 long long a[200001]; 3 int b[200001]; 4 int m,mod; 5 int find(int l,int r,long long x) 6 { 7 if(l>=r-1) 8 if(a[r]>=x) 9 return r; 10 else 11 return l; 12 int mi

[BZOJ1012][JSOI2008]最大数maxnumber 线段树

没什么好说的--线段树维护区间就行了.第一次居然写错了,真丢人. 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 ll inline readll(){ 7 ll Num;char ch; 8 while((ch=getchar())<'0'||ch>'9');Num=ch-'0'; 9

BZOJ 1012: [JSOI2008]最大数maxnumber 单调栈

单调栈 1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 4988  Solved: 2252 [Submit][Status][Discuss] Description 现在请求你维护一个数列,要求提供以下两种操作: 1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度. 2. 插入操作.语法:A n 功能:将n加上t,其中

BZOJ 1012: [JSOI2008]最大数maxnumber 单调队列/线段树/树状数组/乱搞

1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 4750  Solved: 2145[Submit][Status][Discuss] Description 现 在请求你维护一个数列,要求提供以下两种操作: 1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度. 2. 插入操作.语法:A n 功能:将n加上t,其中t是最近一

[JSOI2008]最大数maxnumber(栈&amp;二分查找)

题目链接:1012: [JSOI2008]最大数maxnumber 题意 中文题,点链接看吧,就不copy了. 思路 打眼一看立刻就想到线段树,但本题的区间最值查找每次都是在查后L位,感觉用线段树有些大材小用了. 再仔细想想,发现,如果倒数第i个比倒数第i+1个数小,那么第i个数是没有用的,任意查询的最值都不会是它,因为查的是后L个嘛. 所以呢,我们我以维护一个栈,每次添加新元素时,将其与栈顶元素比较,若栈顶元素小,即无用了,那就出栈,否则,就将新元素入栈. 在查询时直接对栈里元素进行二分查找就