嘛又是看错题了... 话说回来网上的题解都是些啥..

Problem

https://www.luogu.org/problemnew/solution/P3522
$n\leq 10^6$

Solution

因为是连续一段区间所以尺取。
发现区间合法的条件是对于任意 $i< j$，有 $l_i\leq r_j$。
这里请自己手画一下图，当然应该都会发现这个规律。

然后移动 $R$ 指针的话，查询区间 $[L, R)$ 的最大的 $l$ 是不是大于 $r_R$ 就行了。

这玩意可以用单调队列维护。

是傻逼题呢，但我为什么没想出来呢。

因为我太菜了呀。

// Code by ajcxsu
// Problem: TEM

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
int qu[N], pos[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    int l=1;
    int nl, nr, h, t, ans=0;
    h=t=0;
    for(int i=1;i<=n;i++) {
        cin>>nl>>nr;
        while(l<i && qu[h]>nr) {
            l++;
            while(h!=t && pos[h]<l) h++;
        }
        while(h!=t && nl>qu[t-1]) t--;
        qu[t]=nl, pos[t++]=i;
        ans=max(i-l+1, ans);
    }
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3522.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆