题目描述
给出 \(n\) 个数所在区间，求最长可能不降区间。
思路
首先，我们要解决不降的问题，如何才能保证两个相邻区间选数可能不降，不难发现，只要前一个数的最大值大于等于后一个数的最小值即可，即 \(r_{i-1} \ge l_i\)。
然后，因为我们要求的是一段一段连续的区间，所以我们就要维护当前点加入后的区间头、区间尾和区间元素个数，这不就是一个滑动窗口问题嘛，我们使用单调队列来维护，当第 \(i\) 个元素入队时，如果对头元素的最小值大于当前元素最大值，那么肯定不能构成不降序列，对头元素出队，当队尾元素最小值小于当前元素最小值时，在后续匹配中一定当前元素比队尾元素更加有效，因为大于当前元素的一定也大于队尾元素，而小于当前元素的不一定小于队尾元素，所以队尾元素出队。
最后，我们考虑怎么维护区间元素个数，设区间元素个数为 \(len\)，当队尾出队时，新入队的元素 \(i\) 可以理解为把上一个队尾元素挤出去了，但实际上运算时还是需要算上这个元素，那么 \(i\) 就同样也要表示队尾元素的值，队尾元素就变成了 \(i\) 元素的一部分，用 \(f_i\) 表示第 \(i\) 个元素所表示的值，那么上述过程就可以表示为 \(f_i=f_i+f_{q_{tail}}\)，出队时一个元素所表示的所有值都要减去，即为 \(len=len-f_{q_{head}}\)，至此，本题完。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e6+10;
int n;
int l[M],r[M];
ll f[M];
deque<int> q;
int main()
{int ans=0,len=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&l[i],&r[i]);}for(int i=1;i<=n;i++){f[i]=1;while(!q.empty()&&r[i]<l[q.front()]) { len-=f[q.front()];q.pop_front();}while(!q.empty()&&l[i]>=l[q.back()]) {f[i]+=f[q.back()];q.pop_back();}q.push_back(i);len++;ans=max(ans,len);}printf("%d",ans);return 0;
}