单调栈的运用-bzoj1012(代码转载-http://hzwer.com/1130.html)
2024-08-30 09:13:16
Description
现在请求你维护一个数列,要求提供以下两种操作: 、 查询操作。语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。 、 插入操作。语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个数。 Input
第一行两个整数,M和D,其中M表示操作的个数(M <= ,),D如上文中所述,满足( Output
对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。 Sample Input A
Q
A
Q
Q
Sample Output
单调栈解法:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,d,t;
int top,len,a[],num[];
int main()
{
int x;char ch[];
scanf("%d%d",&n,&d);
while(n--)
{
scanf("%s%d",ch,&x);
if(ch[]=='A')
{
x=(x+t)%d;
num[++len]=x;//存储原始数据
while(top&&num[a[top]]<=x)top--;// a[]数组维护单调减队列(a[]储存单调数列在原始数据的位置)
a[++top]=len;
}
else{
int y=lower_bound(a+,a+top+,len-x+)-a;
t=num[a[y]];
printf("%d\n",t);
}
}
return ;
}
解法二: 线段树。维护区间最大值;
最新文章
- 第3月第27天 uitableviewcell复用
- python 日期计算案例
- 解决webstorm卡顿问题
- matlab FDR校正
- Kotlin &; Vertx 构建web服务
- vs2012无法启动已配置的开发Web服务器
- Apache Mina 入门实例
- multi-cursor
- 常用PHP框架功能对比表
- hibernate - 何时关闭数据库
- C++变量的“总分性”(Mereology)
- C#中方法Show.和ShowDialog的使用区别
- linux文件系统拓展属性
- MyEclipse中Source Folder,package,folder的区别
- python面向对象进阶
- P2279 [HNOI2003]消防局的设立 贪心or树形dp
- reduction_indices in tensorflow
- CVE-2017-12149漏洞利用
- android 开发 实现一个activity变成dialog对话框
- 反接保护电路 Reverse Voltage Protection
热门文章
- 牛客网 PAT 算法历年真题 1010 : 月饼 (25)
- Talend 从Excel导入Saleforce数据(二) TMAP是精髓
- Win10系列:VC++调用自定义组件1
- JXL生成Excel,并提供下载(1:生成Excel)
- Factory,工厂设计模式,C++描述
- 十一. Python基础(11)—补充: 作用域 & 装饰器
- 2.15 C++常量指针this
- 2.5 C++类class和结构体struct区别
- RandomStringUtils的使用
- 关于jvm钩子 Runtime.getRuntime().addShutdownHook