bzoj 2369&2687: 区间 cdq分治+决策单调性

题意：

对于一个区间集合{A1,A2……AK}(K>1，Ai<>Aj{i<>j})，我们定义其权值 W=|A1∪A2∪……∪AK|*|A1∩A2∩……AK|当然，如果这些区间没有交集则权值为0。 给你N个（1<N<=10^6）各不相同的区间，请你从中找出若干个区间使其权值最大。 第一行N,接下来N行 l r(1<=l<r<=10^6)

分析： 显然取一堆区间的权值等价于只取最左边和最右边的区间，所以答案最多只用选两个区间。

考虑先把存在包含关系的区间去掉，然后把这个区间与任意一个包含它的区间算一遍权值加到ans里面。注意这里不用找包含它的最大的区间来与它算答案，因为若A包含C，B包含C，则选A和B一定比选A和C或B和C优。

这样我们就得到了m个左端点单调不降，右端点单调不降的区间。考虑每一个区间i所对应的最优决策区间wi(wi<i)，通过推理可以得到wi是单调不降的，那么就可以用cdq来做了。

注意这题有些区间因为与其他区间没有相交，所以其并没有最优决策区间，这种情况要特判掉。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=1000005;

int n;
LL f[N];
struct lin{int l,r;}a[N];

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

bool cmp(lin a,lin b)
{
	return a.l<b.l||a.l==b.l&&a.r<b.r;
}

LL get_ans(int j,int i)
{
	return (LL)(a[i].r-a[j].l)*max(a[j].r-a[i].l,0);
}

void solve(int l,int r,int L,int R)
{
	if (l>r) return;
	if (L==R)
	{
		for (int i=l;i<=r;i++) f[i]=get_ans(L,i);
		return;
	}
	int mid=(l+r)/2,pos=0;LL mx=0;
	for (int i=L;i<=min(R,mid-1);i++)
	{
		LL w=get_ans(i,mid);
		if (w>mx) mx=w,pos=i;
	}
	f[mid]=mx;
	if (mx) solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
	else solve(l,mid-1,L,R),solve(mid+1,r,L,R);
}

int main()
{
	n=read();
	for (int i=1;i<=n;i++) a[i].l=read(),a[i].r=read();
	sort(a+1,a+n+1,cmp);
	LL ans=0;
	int pos=1,mx=a[1].r,m=n;
	for (int i=2;i<=n;i++)
		if (a[i].r<=mx) m--,ans=max(ans,(LL)(a[i].r-a[i].l)*(a[pos].r-a[pos].l)),a[i].l=1e7;
		else pos=i,mx=a[i].r;
	sort(a+1,a+n+1,cmp);
	n=m;
	solve(2,n,1,n);
	for (int i=2;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}