P5896 [IOI2016]aliens

· · 题解

P5896 [IOI2016]aliens

一个 m\times m 的网格图上有 n 个关键点，要求选至多 k 个对角线为主对角线的正方形去覆盖它们。问这些正方形最少要覆盖多少个方格。

考虑 wqs 二分。设 F(i) 用恰好 i 个正方形覆盖关键点，最少覆盖多少小方格。G(i)\gets F(i)+c\cdot i，当 c=0 时显然最优的 i 为 n。随着 c 的增大，最优的 i 会越来越小。

考虑将左上角为 (l,l) 右下角为 (r,r) 的正方形转化为区间 [l,r]。对于一个关键点 (i,j)，记 u=\min(i,j),v=\max(i,j)，则可以被 l\leq u\leq v\leq r 的区间 [l,r] 覆盖。

类似 P6047 丝之割，若 (u_i,v_i),(u_j,v_j) 满足 u_i\leq u_j 且 v_i\geq v_j，那么 j 显然是无用的，因为覆盖 i 的同时一定能覆盖 j。将没有的关键点去掉，按 u 排序，v 也单调递增。

设 f_i 表示覆盖前 i 个有用关键点，最少覆盖多少个方格。同时记录用了多少个区间。f_i=\min\limits_{0\leq j<i}\{f_j+(v_i-u_{j+1}+1)^2-\max(0,v_j-u_{j+1}+1)^2+c\}，斜率优化：\underline{f_j+u_{j+1}^2-2u_{j+1}-\max(0,v_j-u_{j+1}+1)^2}_{\ y}=\underline{2v_i}_{\ k}\underline{u_{j+1}}_{\ x}+\underline{f_i-v_i^2-2v_i-1-c}_{\ b}。

时间复杂度 \mathcal O(n\log m^2)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m,k,cnt,g[N],q[N];
ll f[N],ans;
struct seg{int l,r;}a[N];
ll sq(int x){return 1ll*x*x;}
ll get(int i){
    return f[i]+sq(a[i+1].l)-2*a[i+1].l-sq(max(0,a[i].r-a[i+1].l+1));
}
double slope(int i,int j){
    return 1.0*(get(i)-get(j))/(a[i+1].l-a[j+1].l);
}
bool ok(ll c){
    int l=0,r=0;
    for(int i=1;i<=n;i++){
        while(l<r&&slope(q[l],q[l+1])<2*a[i].r) l++;
        f[i]=f[q[l]]+sq(a[i].r-a[q[l]+1].l+1)-sq(max(0,a[q[l]].r-a[q[l]+1].l+1))+c,g[i]=g[q[l]]+1;
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--;
        q[++r]=i;
    }
    if(g[n]<=k) ans=f[n]-c*k;
    return g[n]<=k;
}
signed main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
        if(a[i].l>a[i].r) swap(a[i].l,a[i].r);
    }
    sort(a+1,a+1+n,[](seg x,seg y){return x.l!=y.l?x.l<y.l:x.r>y.r;});
    for(int i=1,r=-1;i<=n;i++)
        if(a[i].r>r) r=a[i].r,a[++cnt]=a[i];
    n=cnt,a[0].r=-1;
    ll l=0,r=1ll*m*m;
    while(l<=r){
        ll mid=(l+r)/2;
        if(ok(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}