BZOJ2276：[POI2011]Temperature

浅谈队列：https://www.cnblogs.com/AKMer/p/10314965.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2276

假设一段区间满足不降的要求，那么充要条件是\(l_{max}<=r_{min}\)

所以我们用单调队列维护\(l\)的最大值然后更新答案即可。

时间复杂度：\(O(n)\)

时间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=1e6+5;

int n,head,tail,ans,pos;
int l[maxn],r[maxn],list[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

int main() {
    n=read();
    for(int i=1;i<=n;i++)
        l[i]=read(),r[i]=read();
    for(int i=1;i<=n;i++) {
        while(head!=tail&&l[list[tail-1]]<l[i])tail--;
        while(head!=tail&&l[list[head]]>r[i])pos=list[head++];
        list[tail++]=i;ans=max(ans,i-pos);
    }
    printf("%d\n",ans);
    return 0;
}

BZOJ2276：[POI2011]Temperature

原文：https://www.cnblogs.com/AKMer/p/10327234.html