ZigZagK

Never give up fighting!

[决策单调性]BZOJ2369【区间】题解

题目概述

\(n\) 个区间 \(A_i=[L_i,R_i]\) ,现在选 \(m\)\((m>1)\) 区间,贡献为 \(|A_{k_1}\cap A_{k_2}\cap A_{k_3}\cdots A_{k_m}|\times|A_{k_1}\cup A_{k_2}\cup A_{k_3}\cdots A_{k_m}|\) ,求最大贡献。

解题报告

显然最大贡献是只选两个区间,所以我们先把区间排序,去掉被包含的区间(注意去重时也需要计算贡献),然后就可以定义 \(f_i=max\{(R_j-L_i)(R_i-L_j)|j<i\}\) 表示 \(i\) 的最大贡献。

决策单调性是什么呢?和斜率优化类似,如果 \(j\) 对于 \(k\)\(i\) 好能够推出对于 \(t(t>k)\) \(j\) 也比 \(i\) 好,就说明决策点是单调的,这样就可以减少很多没有必要的枚举。

对于这题,令 \(i<j<k<t\) ,假设 \(j\)\(i\) 好,那么: \[
(R_k-L_j)(R_j-L_k)>(R_k-L_i)(R_i-L_k)\\
R_jR_k-R_kL_k-R_jL_j+L_jL_k>R_iR_k-R_kL_k-R_iL_i+L_iL_k\\
R_k(R_j-R_i)+L_k(L_j-L_i)>R_jL_j-R_iL_i\\
\because L_t>L_k,R_t>R_k\\
R_t(R_j-R_i)+L_t(L_j-L_i)>R_jL_j-R_iL_i\\
(R_t-L_j)(R_j-L_t)>(R_t-L_i)(R_i-L_t)\\
\]

所以满足决策单调性,我们就可以分治了!\(Solve(L,R,l,r)\) 表示求出 \(f_{[L,R]}\) ,决策点范围在 \([l,r]\) 。那么我们可以先求出 \(f_{mid}\) 的决策点 \(pos\) ,然后 \(Solve(L,mid,l,pos),Solve(mid+1,R,pos,r)\) 就行了。

注意决策单调性并不一定都能够用分治,因为很明显 \(f\)\(Solve\) 之前是未知的,所以如果 \(f\) 的转移方程中包含 \(f\) 就不能够用分治了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long long LL;
const int maxn=1000000;

int n;LL ans;pair<int,int> s[maxn+5];bool vis[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+ch-48,ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline bool cmp(pair<int,int> a,pair<int,int> b) {return a.fr<b.fr||a.fr==b.fr&&a.sc>b.sc;}
#define val(i,j) ((LL)(s[j].sc-s[i].fr)*(s[i].sc-s[j].fr))
LL Solve(int L,int R,int l,int r){
    if (L==R) {LL MAX=0;for (int i=l;i<=r&&i<L;i++) MAX=max(MAX,val(i,L));return MAX;}
    int mid=L+(R-L>>1);LL MAX=0;int pos=mid;
    for (int i=l;i<=r&&i<mid;i++) if (val(i,mid)>MAX) MAX=val(i,mid),pos=i;
    return max(MAX,max(Solve(L,mid,l,pos),Solve(mid+1,R,pos,r)));
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) readi(s[i].fr),readi(s[i].sc);sort(s+1,s+1+n);
    for (int i=1,j;i<=n;i=j)
        for (j=i+1;j<=n;vis[j++]=true){
            if (s[j].sc>s[i].sc) break;
            ans=max(ans,(LL)(s[i].sc-s[i].fr)*(s[j].sc-s[j].fr));
        }
    for (int tot=n,i=(n=0,1);i<=tot;i++) if (!vis[i]) s[++n]=s[i];
    if (n==1) return printf("%lld\n",ans),0;
    return printf("%lld\n",max(ans,Solve(2,n,1,n-1))),0;
}
点赞

发表评论

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

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]