题解：P17741 [ICPC 2019 Xuzhou R] K-rectangle

· · 题解

小朋友们你们好啊，我比较喜欢小常数多哥哥算法，所以我使用 CDQ 分治+李超线段树 过了这道题。

首先容易发现矩形之间交叉一定不优，所以我们不难写出一个非常暴力的 O(n^2) DP。具体地，设 dp_i 表示前 i 个点已经被覆盖的最小代价。则有：

dp_i=\min_{j=0}^{i-1}\{dp_j+(x_i-x_{j+1}+k)\times\max_{t=j+1}^i y_t\}.

也就是，枚举最后一个矩形覆盖了多少个点，直接进行转移。

接下来考虑优化。发现这个转移式子的形式非常像一个斜率优化，但是这里有个区间 \max 是动态的。如果我们能把这个 \max 转成静态，即只与 i 和 j 有关的值，就可以斜率优化了。

假设我们在 i 和 j 之间找了一个点 j\le mid<i。那么此时，\max_{t=j+1}^i y_t 就可以被拆成两部分，即 \max_{t=j+1}^{mid} y_t 和 \max_{t=mid+1}^i y_t。

我们定义 A_j=\max_{t=j+1}^{mid} y_t，B_i=\max_{t=mid+1}^i y_t。其中约定 A_{mid}=0。那么此时，转移式就是：

dp_i=\min_{j=0}^{i-1}\{dp_j+(x_i-x_{j+1}+k)\times\max\{A_j,B_i\}\}.

分类讨论 A_j 和 B_i 的大小即可。也就是说，假设我们可以找到一个 k，就可以统一处理 k 左边的点向 k 右边的点的转移。考虑 CDQ 分治。

我们希望调用 CDQ(l,r) 来算出 dp_{l} 到 dp_{r} 的值。假设现在已经处理完了 dp_{l} 到 dp_{mid} 的值，想要处理 [l,mid] 到 [mid+1,r] 的转移。

仿照上面的做法，我们定义 A_j=\max_{t=j+1}^{mid} y_t，B_i=\max_{t=mid+1}^i y_t。

此时，A 序列的值单调不增，B 序列的值单调不降。

我们要分情况讨论转移，即分当 A_j\le B_i 和 A_j\ge B_i 两种情况转移。

当 A_j\le B_i 时：

dp_i=\min_{j=0}^{i-1}\{dp_j+(x_i-x_{j+1}+k)\times B_i\}.

因为 A 序列的值单调不增，B 序列的值单调不降，所以固定 i 不变时，所有满足 A_j\le B_i 的 j 一定是一段以 mid 结束的后缀。考虑双指针维护。

此时就是个斜率优化模板了。我喜欢轮椅数据结构，所以我使用了李超树。那么这个转移式的直线斜率就是 x_{j+1}，截距是 dp_j。此时 dp_i=\text{query}(-B_i)+B_i\times (x_i+k)。

当 A_j\ge B_i 时：

dp_i=\min_{j=0}^{i-1}\{dp_j+(x_i-x_{j+1}+k)\times A_j\}.

因为 A 序列的值单调不增，B 序列的值单调不降，所以固定 i 不变时，所有满足 A_j\ge B_i 的 j 一定是一段以 l 开始的前缀。同样可以使用双指针维护。

那么这个转移式的直线斜率就是 A_j，截距是 dp_j+(k-x_{j+1})\times A_j。此时 dp_i=\text{query}(x_i)。

然后就做完了。时间复杂度为 O(n\log n\log V)，V 表示值域，大概在 2\times 10^6 左右。有点简单 /jk。

:::success[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=8e5+10,inf=5e17+10,H=1e6+10,V=2e6+20;

namespace IO{
    const static int _M=1e6+5,_K=2e6+5;
    char ibuf[_K],obuf[_K],_st[_K],*p1(0),*p2(0);
    static int _cnt=0,_top=0;
    inline void flush(){return fwrite(obuf,1,_cnt,stdout),_cnt=0,void();}
    struct AutoFlush{~AutoFlush(){flush();}}flusher;
    inline char gc(){return (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,_K,stdin),p1==p2)?EOF:*p1++);}
    template<typename T>inline void read(T&x){
        x=0;char c;bool f=0;
        do{c=gc();if(c=='-') f=1;}while(c<48);do{x=(x<<3)+(x<<1)+(c^48);c=gc();}while(c>=48);
        return(f?x=~x+1,void():void()),void();
    }
    template<typename T>inline void readmod(T&x,ll mod){
        x=0;char c;
        do{c=gc();}while(c<48);do{x=((x<<3)+(x<<1)+(c^48))%mod;c=gc();}while(c>=48);
        return;
    }
    inline void pc(char c){obuf[_cnt++]=c;if(_cnt>=_M)flush();return;}
    inline void ps(string s){for(auto c:s)obuf[_cnt++]=c;if(_cnt>=_M)flush();return;}
    template<typename T>inline void write(T x,char c='\0'){
        if(x<0) pc('-'),x=-x;
        do{_st[++_top]=(x%10)|48;}while(x/=10);while(_top)pc(_st[_top--]);
        return(c?pc(c):void()),void();
    }
}using namespace IO;

ll n,k,x[N],y[N],a[N],b[N],dp[N];

struct sgt{

    ll cnt=0,tot=0,root=0,now=0;

    struct Line{ll k,b;}L[N<<2]={0,inf};
    struct node{ll ls,rs,num,tag;}tr[N<<2];

    #define ls tr[p].ls
    #define rs tr[p].rs
    #define num tr[p].num
    #define tag tr[p].tag

    inline void clear(){now++,tot=0;return;}
    inline ll calc(ll id,ll x){return L[id].k*(x-H)+L[id].b;}

    inline void upd(ll &p,ll l,ll r,ll u){

        if(!p) p=++cnt;
        if(tag!=now) return tag=now,num=u,void();

        ll mid=(l+r)>>1;

        ll op1=calc(u,mid),op2=calc(num,mid);
        if(op1<op2) swap(u,num);

        if(l==r) return;

        op1=calc(u,l),op2=calc(num,l);
        if(op1<op2) upd(ls,l,mid,u);

        op1=calc(u,r),op2=calc(num,r);
        if(op1<op2) upd(rs,mid+1,r,u);

        return;
    }

    inline void add(ll k,ll b){L[++tot]={k,b};upd(root,1,V,tot);}

    inline ll query(ll x,ll p,ll l,ll r){

        if(!p||tag!=now) return inf;

        ll mid=(l+r)>>1,ans=calc(num,x);

        if(l==r) return ans;
        else if(mid>=x) return min(ans,query(x,ls,l,mid));
        else return min(ans,query(x,rs,mid+1,r));
    }
}T;

inline void CDQ(ll l,ll r){

    if(l==r) return;
    ll mid=(l+r)>>1;

    CDQ(l,mid);

    a[mid]=0;
    for(int i=mid-1;i>=l;i--) a[i]=max(y[i+1],a[i+1]);

    b[mid]=0;
    for(int i=mid+1;i<=r;i++) b[i]=max(y[i],b[i-1]);

    T.clear();

    ll j=l;
    for(int i=r;i>mid;i--){

        while(j<=mid&&a[j]>=b[i]) T.add(a[j],dp[j]+(k-x[j+1])*a[j]),j++;
        dp[i]=min(dp[i],T.query(x[i]+H,T.root,1,V));
    }

    T.clear();

    j=mid;
    for(int i=mid+1;i<=r;i++){

        while(j>=l&&a[j]<=b[i]) T.add(x[j+1],dp[j]),j--;
        dp[i]=min(dp[i],T.query(H-b[i],T.root,1,V)+b[i]*(x[i]+k));
    }

    return CDQ(mid+1,r);
}

int main(){

    read(n),read(k);
    for(int i=1;i<=n;i++) read(x[i]),read(y[i]),dp[i]=inf;

    CDQ(0,n);
    write(dp[n],'\n');

    return 0;
}

:::