Miku

莫名其妙每一天

如果一天满足和前面的连续一些天可能不下降，那么它的最大气温一定不小于之前序列的每一天的最小气温

然后这东西用单调队列维护

再开一个队列维护这一段序列的堆头

就Ac了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
long long t[1000001][2];
int n;
int ans=1;//至少为1 
deque <int> q,q2;
int x;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&t[i][0],&t[i][1]);
    for(int i=1;i<=n;++i){
        if(q.empty()){
            q.push_back(i);
            q2.push_back(i);
        }else{
            while(!q.empty()&&t[q.front()][0]>t[i][1]){          
                q.pop_front();
                q2.pop_front();
            }
            x=i;
            while(!q.empty()&&t[q.back()][0]<=t[i][0]){
                x=q2.back();//继承被踢出的点的编号 
                q2.pop_back();
                q.pop_back();
            }
            q.push_back(i);
            q2.push_back(x);
            ans=max(ans,i-q2.front()+1);
        }
    }
    ans=max(ans,n-q2.front());
    cout<<ans;
    return 0;
}