link
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;
}