洛谷P1198 [JSOI2008]最大数(线段树/单调栈)
2024-10-20 09:33:28
题目链接:
https://www.luogu.org/problemnew/show/P1198
题目描述
现在请求你维护一个数列,要求提供以下两种操作:
1、 查询操作。
语法:Q L
功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。
限制:LL不超过当前数列的长度。(L > 0)(L>0)
2、 插入操作。
语法:A n
功能:将nn加上tt,其中tt是最近一次查询操作的答案(如果还未执行过查询操作,则t=0t=0),并将所得结果对一个固定的常数DD取模,将所得答案插入到数列的末尾。
限制:nn是整数(可能为负数)并且在长整范围内。
注意:初始时数列是空的,没有一个数。
输入输出格式
输入格式:
第一行两个整数,MM和DD,其中MM表示操作的个数(M \le 200,000)(M≤200,000),DD如上文中所述,满足(0<D<2,000,000,000)(0<D<2,000,000,000)
接下来的MM行,每行一个字符串,描述一个具体的操作。语法如上文所述。
输出格式:
对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。
输入输出样例
单调栈解法。因为题目求的是末尾L个数的最大值,利用两个栈分别存储最大值和最大值的位置。然后二分查找。注意二分查找时上界是总得个数减去区间长度,而不是栈的空间减去区间长度,因为不符合栈的数值已经出栈了。
单调栈解法参考自:https://www.luogu.org/blog/user38348/solution-p1198
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
long long Stack[2][200010];
long long cnt=0,top=0;
void add(long long val){
cnt++;
while(Stack[0][top]<val&&(top>0)) top--;
Stack[0][++top]=val;
Stack[1][top]=cnt;
}
long long quiry(long long L){
int l=1,r=top;
int ind=cnt-L+1;
// int ind=top-L+1;
while(l<r){
int mid=(l+r)>>1;
if(Stack[1][mid]<ind) l=mid+1;
else r=mid;
}
return Stack[0][l];
}
int main(int argc, char** argv) {
int M;long long D;
scanf("%d %lld",&M,&D);
long long t=0;
while(M--){
char c;
long long d;
cin>>c>>d;
if(c=='A'){
add((t+d)%D);
}
else if(c=='Q'){
t=quiry(d);
printf("%lld\n",t);
}
}
return 0;
}
线段树解法,维护区间的最大值。
#include <iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=200010*4;
ll Max[maxn]; void add(int p,int l,int r,int x,ll c){
if(l==r){
Max[p]=c;return;
}
int mid=(l+r)>>1;
if(x<=mid) add(p<<1,l,mid,x,c);
else add(p<<1|1,mid+1,r,x,c);
Max[p]=max(Max[p<<1],Max[p<<1|1]);
}
int quiry(int p,int l,int r,int a,int b){
if(a>r||b<l) return -1e8;
if(a<=l&&r<=b){
return Max[p];
}
int mid=(l+r)>>1;
return max(quiry(p<<1,l,mid,a,b),quiry(p<<1|1,mid+1,r,a,b));
}
int main(int argc, char** argv) {
int M,D;
scanf("%d %d",&M,&D);
fill(Max,Max+maxn,-1e8);
ll t=0;
int x=0;
while(M--){
char c;int d;
cin>>c>>d;
if(c=='A'){
x++;
ll num=(t+d)%D;
add(1,1,200010,x,num);
}else if(c=='Q'){
t=quiry(1,1,200010,x-d+1,x);
printf("%lld\n",t);
}
}
return 0;
}
最新文章
- JDBC Tutorials: Commit or Rollback transaction in finally block
- Android基础总结(三)
- jenkins2 hello pipeline
- 在windows下使用gnu的工具
- 网站不能访问(httperrLog【Timer_MinBytesPerSecond】【Timer_ConnectionIdle】)(转载)
- Oracle数据库查询语句
- Loadrunner:POP3协议录制收信,使用foxmail录制到的脚本为空
- C#去掉周六周日的算法
- 内核源码分析之进程地址空间(基于3.16-rc4)
- Linux命令(5):cp命令
- 网站加载有商务通、商桥,定义js函数触发快商通代码
- 简单聊聊TestNG中的并发
- React的学习(下)
- 201521123113《Java程序设计》第11周学习总结
- 数据结构--二叉查找树的java实现
- 发现----Android Demo
- centos 6.8 搭建svn服务器
- gitlab 数据同步
- bootstrap-table插件数据加载方式
- 使用paramiko远程登录并执行命令脚本
热门文章
- screw一键生成数据库文档
- 详解Java中的IO输入输出流!
- vue第八单元(组件通信 子父,父子组件通信 自定义事件 事件修饰符 v-model props验证 )
- matplotlib的学习10-Contours 等高线图
- 初识SylixOs
- 数据库SQL调优的几种方式 EFcore读的情况下使用 AsNoTracking非跟踪查询
- Java获取X509证书里的指纹(SHA-1)从pxf文件里面
- [leetcode]79.Search Word 回溯法
- IDEA 使用Git clone项目【建议】
- Java学习日报9.30