P1198 [JSOI2008] 最大数

embedded/2024/11/28 18:26:32/

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/embedded/141234.html

相关文章

Android 14之HIDL转AIDL通信

Android 14之HIDL转AIDL通信 1、interface接口1.1 接口变更1.2 生成hidl2aidl工具1.3 执行hidl2aidl指令1.4 修改aidl的Android.bp文件1.5 创建路径1.6 拷贝生成的aidl到1和current1.7 更新与冻结版本1.8 编译模块接口 2、服务端代码适配hal代码修改2.1 修改Android.bp的hidl依…

全渠道供应链变革下“小程序 AI 智能名片 S2B2C 商城系统”的赋能与突破

摘要&#xff1a;本文围绕全渠道供应链构建这一核心主题&#xff0c;剖析零售企业面临的挑战与机遇&#xff0c;着重探讨在整合采购、营销、仓储、物流等多环节进程中&#xff0c;物流环节整合困境及全渠道模式应对策略。深入研究“小程序 AI 智能名片 S2B2C 商城系统”如何契合…

Java入门:17.正则表达式,String的intern方法,StringBuilder可变字符串特点与应用,+连接字符串特点--001

1 String中的常用方法2 1.1 split方法 将字符串按照指定的内容进行分割&#xff0c;将分割成的每一个子部分组成一个数组 分割内容不会出现在数组中 实际上该方法不是按照指定的简单的符号进行分割的&#xff0c;而是按照正则表达式进行分割 1.2 正则表达式 用简单的符号组…

[高阶数据结构四] 初始图论

1.前言 本篇着重讲解图的相关知识&#xff0c;大家跟随我的脚步往下阅读。 本章重点&#xff1a; 本章着重讲解图的基本知识&#xff0c;图的存储结构&#xff1a;邻接矩阵&#xff0c;邻接表以及图的模拟实现 2.图的基本概念 图是由顶点集合及顶点间的关系组成的一种数据结构…

Tri Mode Ethernet MAC IP核详解

本文对 Vivado 的三速 MAC IP 核&#xff08;Tri Mode Ethernet MAC&#xff0c;TEMAC&#xff09;进行介绍。 在自行实现三速以太网 MAC 控制器时&#xff0c;GMII/RGMII 接口可以通过 IDDR、ODDR 原语实现&#xff0c;然而实际使用中自己实现的模块性能不是很稳定&#xff08…

读书笔记_《创华为.任正非传》_精华书摘

人生经历 43岁&#xff0c;开始创建华为 爷爷:金华火腿乡间厨师 父亲: 1910年生&#xff0c;北平民大经济系读书->职业学校任教->国民党兵工厂会计&#xff0c;组织读书会(读书会后来有很多人在新中国成立后成为高级干部。) 母亲: 高中毕业&#xff0c;乡村教师&#xf…

IAR Embedded Workbench for Arm 使用技巧

1 C-RUN C-RUN直接集成在IAR Embedded Workbench for Arm中&#xff0c;在代码执行过程中进行动态代码分析&#xff0c;及时发现运行时发现的实际错误。   C-RUN可以检查算术问题、边界问题和堆完整性&#xff0c;各个功能特点&#xff1a; 算术问题&#xff1a; 包括溢出、…

强制大模型输出json

一个是api里面有一个return_json的选项设置为True. 这个要看大模型厂商是否提供这个选项了.是利用提示词: 返回信息格式为: json格式, 包含一个字段code用整数1-4表示函数编号, 一个字段input用一个字符串表示函数的输入参数. 请只返回json, 返回其他数据都会得到批评 这个句子…