【BZOJ2369】区间

  首先肯定是只选两个区间时答案。

  如果一个区间被另一个更大的区间包含，则这个区间和其他区间的权值一定比那个大的区间和其他区间的权值小。这个被包含的区间对答案的贡献只有它和把它包含的区间的权值。

  第一步先把那些被包含的区间对答案的贡献处理掉，第二步算那些互不包含的区间的权值。

  两步都用单调队列维护已经遍历过的可以取得最大值的区间。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000010;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Segment {int l,r;}S[maxn],Q[maxn];
bool cmp(const Segment &a,const Segment &b) {return a.l<b.l || a.l==b.l && a.r>b.r;}

int qn,n;
LL ans;

void Init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) read(S[i].l),read(S[i].r);
	sort(S+1,S+1+n,cmp);
	int cnt=0;qn=0;
	for (int i=1;i<=n;i++)
		if (S[i].l>S[cnt].l && S[i].r>S[cnt].r)
		{
			S[++cnt]=S[i];
			while (qn && Q[qn].r-Q[qn].l<=S[i].r-S[i].l) qn--;
			Q[++qn]=S[i];
		}
		else
		{
			int fl=1,fr=qn,mid;
			while (fl<fr)
				if (Q[mid=(fl+fr)>>1].r>=S[i].r) fr=mid;else fl=mid+1;
			ans=max(ans,(LL)(Q[fl].r-Q[fl].l)*(S[i].r-S[i].l));
		}
	n=cnt;
}

#define l1 (Q[qn].l)
#define r1 (S[i].r)
#define l2 (S[i].l)
#define r2 (Q[qn].r)

void Solve()
{
	qn=0;
	for (int i=1;i<=n;i++)
	{
		while (qn && r1-l2>=r2-l1) ans=max(ans,(LL)(r1-l1)*(r2-l2)),qn--;
		ans=max(ans,(LL)(r1-l1)*(r2-l2));
		Q[++qn]=S[i];
	}
}

int main()
{
	Init();
	Solve();
	printf("%lld\n",ans);
	return 0;
}