P3522 [POI2011]TEM-Temperature 题解

P3522 [POI2011]TEM-Temperature

给出 \(N\) 个区间 \([L_i,R_i]\) 表示第 \(i\) 天温度的范围

求出连续的最长上升温度的天数

sol

我们先来考虑一件事情:一段区间唯一的限制是最大的最低温度,如果一天的最大温度小于前面的最大的最低温度,那么这天不能和前面的连起来,必须作为头计算

对于这天后面的天数,显然也不能和这天前面的连起来,最多和这天连起来

那么我们只需要维护一个左端点递增的序列就好了

维护一个单调队列,如果一天的最高温度比之前的最低温度低,那么之前不能练起来,所以 \(hed++\),然后计算答案,如果这天的最低温度比之前的最低温度高,那么之前温度就没有存在的意义了,所以 \(til--\)然后将这天塞入队列。

考虑怎么计算答案,\(q[hed]\) 记录的是能和这天连续的最高的最低温度,所以 \(q[hed-1]\) 记录的就是这段连续的第一天的前一天,就是第一个不能满足条件的,所以答案就是 \(i-q[l-1]\)

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int N,a[maxn],b[maxn],q[maxn];
int main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++) a[i]=read(),b[i]=read();
	int l=1,r=0,ans=0,len;
	for(int i=1;i<=N;i++){
		while(l<=r&&a[q[l]]>b[i])l++;
		len=l>r?1:i-q[l-1];
		ans=ans>len?ans:len;
		while(l<=r&&a[q[r]]<a[i])r--;
		q[++r]=i;
	}
	printf("%d\n",ans);
	return 0;
}
上一篇:2013 Asia Regional Changchun I String 字符串哈希


下一篇:CYQ.Data 支持分布式数据库(主从备)高可用及负载调试