Luogu P3522 [POI2011]TEM-Temperature Answer key

Topic link ：P3522 [POI2011]TEM-Temperature

The question ：

A country has carried out continuous $n$ ( $1\le n\le 1,000,000$） Day temperature measurement , There is an error in the measurement , The result of the measurement is $i$ The temperature is $[l_i,r_i]$ Within the scope of .

Find the longest continuous segment , The temperature may not drop in this section .

It is not difficult to find that the legal range is $\max \{l_i\}>r_{i+1}$

Consider monotonic queue maintenance maxima

Note that the answer should be updated with (i-1)-q[st]+1

Because if there's one $l_i$ Particularly large , Maintain the current legal $l$ All give pop It fell off

The count should not be from now $l_i$ Start , But the last one to be pop Dropped

Use this way q[st] Just right （ My code is (l,r] Of ）

Time complexity $O(n)$

Code ：

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

Reprint please explain the source