P1198 [JSOI2008] 最大数

devtools/2024/11/28 12:37:14/

P1198 [JSOI2008] 最大数icon-default.png?t=O83Ahttps://www.luogu.com.cn/problem/P1198

牵制芝士:单调队列

思路:

我们的任务是找出一个区间最大值的

因为插入的数与上一次的答案有关 所以它是强制在线的(真无语了

我们可以在每次插入时整一个叫做控制区间的东西

用来表示这个数在这一个连续的区间中是最大值

比如 经过处理后输入数列是3,5,4,1,2

那么它们的控制区间就如下表

序号12345
35412
控制区间1~23~34~5

其中 第1个数会被第2个数“控制”

其中 第4个数会被第5个数“控制”

所以它们的区间被“吞并”了

在查询操作时

我们可以对控制区间进行二分 找出它所对应的值

那如何快速得到控制区间呢?

let us梳理一下过程

首先我们将第1个数存入 

在将第2个数存入 发现它之前的数小于它 就往前冲

将第1个数干掉

看到这 你是不是感觉到不太对劲 这不就是我们熟悉的单调队列吗?

之后便豁然开朗了吧

注:记得取模!

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,mod,sum,q[210000],t,cnt,p[210000];
signed main()
{scanf("%lld%lld",&m,&mod);while(m--){char ch;int x;cin>>ch>>x;if(ch=='A'){x+=sum;x%=mod;while(t>0&&q[t]<=x){t--;}q[++t]=x;p[t]=++cnt;}else{int l=1,r=t,st=0;while(l<=r){int mid=(l+r)>>1;if(p[mid]>=cnt-x+1){st=mid;r=mid-1;}else{l=mid+1;}}sum=q[st];printf("%lld\n",q[st]);}}return 0;
}


http://www.ppmy.cn/devtools/137665.html

相关文章

鸿蒙多线程应用-taskPool

并发模型 并发模型是用来实现不同应用场景中并发任务的编程模型&#xff0c;常见的并发模型分为基于内存共享的并发模型和基于消息通信的并发模型。 Actor并发模型作为基于消息通信并发模型的典型代表&#xff0c;不需要开发者去面对锁带来的一系列复杂偶发的问题&#xff0c;同…

深信服技术服务工程师(网络安全、云计算方向)面试题

1.tcp3次握手和四次挥手的过程。 2.简述ospf动态路由。 3.哪些地方用静态路由&#xff0c;哪些地方用动态路由&#xff0c;说说他们的区别 4.在数据包在二层交换机中是如何转发的 5.两个三层交换机如何进行通信 6.trunk和access模式区别 7.对http协议的了解&#xff08;https&a…

数据结构 ——— 归并排序算法的实现

目录 归并排序的思想 归并排序算法的实现 归并排序的思想 将已经有序的子序列合并&#xff0c;得到完全有序的序列&#xff0c;即先使每个子序列有序后&#xff0c;再使子序列段间有序 若将两个有序表合并成一个有序表&#xff0c;称为二路归并 归并排序步骤示意图&#x…

Redis设计与实现第15章 -- 复制 总结(旧版复制 新版复制 部分重同步 复制 心跳检测)

在Redis中&#xff0c;用户可以通过执行SLAVEOF命令或设置slaveof选项&#xff0c;让一个服务器&#xff08;从服务器&#xff09;去复制另一个服务器&#xff08;主服务器&#xff09;&#xff0c;进行复制中的主从服务器双方的数据库将保存相同的数据。 15.1 旧版复制功能的…

一款开源的宝藏聊天机器人Typebot

是否一个人寂寞难耐&#xff0c;是否半夜找不到诉说的对象&#xff0c;是否一个人半夜偷偷买醉&#xff1f;咳咳…跑题了。如果你需要个聊天机器人帮你解决问题&#xff0c;来看看Typebot吧。 介绍 Typebot 是一个功能强大的开源聊天机器人框架&#xff0c;旨在帮助开发者轻…

渗透测试笔记—window基础

声明&#xff1a; 学习视频来自B站up主 【泷羽sec】有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&am…

2024 APMCM亚太数学建模C题 - 宠物行业及相关产业的发展分析和策略 完整参考论文(1)

摘要 近年来,中国宠物食品行业迅速增长,但面临复杂的国际形势和多变的市场环境,因此科学地分析和预测该行业的发展趋势至关重要。本研究通过构建多个机器学习与统计回归模型,量化分析中国宠物食品行业的关键驱动因素,预测未来宠物食品总产值和出口值。 在数据处理部分,…

RK3568平台开发系列讲解(DMA篇)什么是DMA

🚀返回专栏总目录 文章目录 一、什么是DMA二、DMA的产生:背景三、理解 DMA:协处理器沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将带领大家深刻理解DMA。 一、什么是DMA DMA (Direct Memory Access) is used to copy data directly between devices and R…