[BZOJ2369]区间 决策单调性


原题链接
首先得到两个结论:
1.必然存在只选两个区间的最优解;
2.被别的区间包含的区间,对除其父区间外的区间没有贡献.
那么我们将被别的区间包含的区间都去掉顺便更新答案,然后将区间按位置排序,就变成了给每个区间找一个和它一起选答案最大的.这个问题显然具有决策单调性,分治一下即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
using namespace std;
typedef long long ll;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
struct Node
{
    int l,r;
}a[N];
inline bool operator<(const Node a,const Node b)
{
    return a.l<b.l||(a.l==b.l&&a.r>b.r);
}
int n,cnt;
ll ans;
inline ll calc(int i,int j)
{
    return max(0ll,(ll)(a[i].r-a[j].l)*(a[j].r-a[i].l));
}
void cdq(int l,int r,int b,int e)
{
    if(l>r)return;
    int mid=(l+r)>>1,i,p;
    ll maxval=0,tmp;
    for(i=b;i<=min(mid-1,e);++i)
    {
        tmp=calc(i,mid);
        if(tmp>maxval)maxval=tmp,p=i;
    }
    ans=max(ans,maxval);
    if(maxval)cdq(l,mid-1,b,p),cdq(mid+1,r,p,e);
    else cdq(l,mid-1,b,mid-1),cdq(mid+1,r,mid,e);
}
int main()
{
    read(n);
    int i;
    for(i=1;i<=n;++i)read(a[i].l),read(a[i].r);
    sort(a+1,a+n+1);
    cnt=1;
    for(i=2;i<=n;++i)
    {
        if(a[i].r<=a[cnt].r)ans=max(ans,(ll)(a[i].r-a[i].l)*(a[cnt].r-a[cnt].l));
        else a[++cnt]=a[i];
    }
    cdq(1,cnt,1,cnt);
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注