Description：

进行了连续 $n$ 天的温度测量，测量存在误差，测量结果是第 $i$ 天温度在 $[l_i,r_i]$ 范围内。 求最长的连续的一段，满足该段内可能温度不降。

$1\le n \le 10^6$

Solution：

题意就是找一段最长 $[i,j]$ 的满足 $\forall k\in [i,j],r_k\ge \max_{w=i}^{k-1}l_w$ ，看数据范围要求 $O(n)$ 做法，于是我们必须能 $O(1)$ 得到区间最大值，于是用一个 $l$ 单调递减的队列来维护，每次 $\text{pop_front}$ 时更新一下左边界就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int l[MAXN],r[MAXN];

deque<int> q;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d",&l[i],&r[i]);

	int ans = 1;

	int lef = 1;

	for(int i = 1;i <= n;++i)

	{

		while(!q.empty() && l[q.front()] > r[i]){lef = q.front() + 1;q.pop_front();}

		while(!q.empty() && l[q.back()] < l[i])q.pop_back();

		q.push_back(i);

		ans = max(ans,i - lef + 1);

	}

	cout << ans << endl;

	return 0;

}