bzoj 2276 [ Poi 2011 ] Temperature —— 单调队列
2024-09-08 16:48:20
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2276
维护 l 递减的单调队列,队头的 l > 当前的 r 就出队,因为不能是连续一段了;
注意答案是上一个出队的实际后一个位置开始,而不是队头的位置,因为不在队列里的那些位置 l 都比队头小,也是合法的。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=1e6+;
int n,l[maxn],r[maxn],h,t,ans;
struct N{int l,r,pos;}q[maxn];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
h=; t=;
for(int i=;i<=n;i++)
{
while(h<=t&&q[h].l>r[i])h++;
ans=max(ans,i-q[h-].pos);//
while(h<=t&&q[t].l<l[i])t--;
q[++t].l=l[i]; q[t].r=r[i]; q[t].pos=i;
}
printf("%d\n",ans);
return ;
}
最新文章
- C#开发微信门户及应用(19)-微信企业号的消息发送(文本、图片、文件、语音、视频、图文消息等)
- CentOS上yum安装JDK
- Wrangle – 响应式的,触摸友好的多选插件
- AutoHotkey之自问自答
- lsof用法简介
- ViewPager图片轮转带点的
- ✡ leetcode 160. Intersection of Two Linked Lists 求两个链表的起始重复位置 --------- java
- 实现IHttpModule接口,给每个页面输出一段脚本
- Python 时间整理
- 用Canvas制作小游戏——贪吃蛇
- JS获取浏览器可视区域尺寸
- [Javascript] Proper use of console.assert in JavaScript
- Web项目练习总结(错误校正篇)
- css-选择器-优先级
- HTTP Status 404 - No result defined for action com.hebky.oa.classEntity.action.EntitysAction and result input
- Mysql两种存储引擎的优缺点
- Unity之2D Sprite Outline外轮廓效果
- codevs 3981 动态最大子段和
- python——redis
- Django之auth模块
热门文章
- 当点阵字库遇到3D
- ORACLE索引介绍和使用
- 树状数组 &; lowbit()
- HDU - 6264 - Super-palindrome(思维)
- [luogu3573 POI2014] RAJ-Rally (拓扑排序 权值线段树)
- 来说一说chrome扩展和chrome插件到底有什么区别?
- NT9666X调试log
- BZOJ 3747 洛谷 3582 [POI2015]Kinoman
- java json数据转List对象的集合-----阿里巴巴插件---及原生json---JSON 与 对象 、集合 之间的转换 JSON字符串和java对象的互转【json-lib】
- Mysql SQL查询今天、昨天、n天内、第n天------https://blog.csdn.net/baidu_27222643/article/details/60467585