洛谷P3522 [POI2011]TEM-Temperature 题解

题目链接：P3522 [POI2011]TEM-Temperature

题意：

某国进行了连续 $n$ ( $1\le n\le 1,000,000$）天的温度测量，测量存在误差，测量结果是第 $i$ 天温度在 $[l_i,r_i]$ 范围内。

求最长的连续的一段，满足该段内可能温度不降。

不难发现合法区间为 $\max \{l_i\}>r_{i+1}$

考虑单调队列维护最大值

注意答案的更新应该用(i-1)-q[st]+1

因为如果有个 $l_i$ 特别大，把当前维护的合法的 $l$ 都给pop掉了

计数不应当是从现在的 $l_i$ 开始，而是最后一个被pop掉的

这样用q[st]正好（我的代码是(l,r]的）

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
    
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
    
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){
    x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
    
        if(k<0){
    k=-k;pc('-');}
        static T stk[66];T top=0;
        do{
    stk[top++]=k%10,k/=10;}while(k);
        while(top){
    pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)

int n,st,en,res=1,l[N],r[N],q[N];
signed main()
{
    
    read(n); st=en=1;
    for(int i=1; i<=n; i++)
    {
    
        read(l[i]);read(r[i]);
        while(st<en&&l[q[st+1]]>r[i])++st;
        if(st<en)res=max(res,i-q[st]);
        while(st<en&&l[q[en]]<l[i])--en;
        q[++en]=i;
    }
    write(res);
    return 0;
}

转载请说明出处