洛谷3522 [POI2011]TEM-Temperature

题意

有 $N$ 个区间 $[L_i,R_i]$，求最长的连续的一段，使得段内的温度可能不降。

$N\le 10^6$ 。

题解

连续一段 $i..j$ 的终止条件是 $R_j < L_i$ ，所以要使得队头的 $L$ 尽可能大，用单调队列维护 $L$ 的递减序列即可。

因为要求连续，所以把队列末尾退队时需要记录最后一个的位置，并把当前元素放入。

#include<bits/stdc++.h>

using namespace std;

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

const int N=1000005;
int n,ans,L[N],R[N],q[N],f[N];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) L[i]=read(),R[i]=read();
    int l=1,r=1; q[1]=f[1]=1;
    for (int i=2;i<=n;i++)
    {
        while (l<=r && L[q[l]]>R[i]) l++;
        if (l<=r) ans=max(ans,i-q[l]+1);
        int nxt=i;
        while (l<=r && L[q[r]]<=L[i]) nxt=q[r--]; //nxt记录最后一个位置
        L[nxt]=L[i]; //R并不重要所以只继承L
        q[++r]=nxt;
    }
    return !printf("%d",ans);
}