P3522 [POI 2011] TEM-Temperature

题目描述

给出 \(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}}\)，至此，本题完。
代码

[code]#include#define ll long longusing namespace std;const int M=2e6+10;int n;int l[M],r[M];ll f[M];deque q;int main(){        int ans=0,len=0;        scanf("%d",&n);        for(int i=1;i

过来提前占个楼