P8632 题解

· · 题解

传送门。

下文中所有出现的 n 都对应题目中的 L。

设 a_i 为距离公路起点 i 处的总人数，f_{i,1/2/3} 表示前 i 个点中，选了 1/2/3 个点，且选择了点 i，前 i 个点的最小代价。

暴力 dp 转移如下：

答案 ans=\min\limits_{i=1}^{n-1} f_{i,3}+\sum\limits_{j=i+1}^n a_j(n-j)。

直接做是 O(n^2) 的，有 40 分的部分分。

可以把 \sum a_j(i-j) 拆开，令 A_i 为 a_i 的前缀和，B_i 为 i\times a_i 的前缀和：

把只与 i 有关的项移到左边（以下两式省去了 \min）：

将 -A_k 看作斜率，f_{k,1/2}+B_k 看作纵截距，右式就变成了一次函数的形式。现在就是需要支持每次插入一条直线，并查询所有直线在 x=i 时的 y_{\min}。用李超线段树维护，时间复杂度 O(n\log n)。

注意 0 \le d_i \le n。

#include<bits/stdc++.h>
#define il inline
#define int long long
using namespace std;
const int N=1e6+5;
const int inf=1e18;

il int wrd(){
    int x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){x=x*10+c-48,c=getchar();}
    return x*f;
}

int n,m,a[N],A[N],B[N],ans=inf,dp[N][4];

struct seg{
    int k,b;
}sg1[N],sg2[N];

int val(int o,int x,bool op){
    if(o==-1) return inf;
    return op ? sg2[o].k*x+sg2[o].b : sg1[o].k*x+sg1[o].b;
}

int s[N<<2][2];

#define ls (t<<1)
#define rs (t<<1|1)
#define md ((l+r)>>1)

void modify(int l,int r,int t,int u,int op){
    int &v=s[t][op];
    if(val(v,md,op)>val(u,md,op)) swap(u,v);
    if(val(v,l,op)>val(u,l,op)) modify(l,md,ls,u,op);
    if(val(v,r,op)>val(u,r,op)) modify(md+1,r,rs,u,op);
}

int qry(int l,int r,int t,int x,int op){
    int ans=val(s[t][op],x,op);
    if(l==r) return ans;
    return min(ans,x<=md ? qry(l,md,ls,x,op) : qry(md+1,r,rs,x,op));
}

signed main(){
    m=wrd(),n=wrd();
    while(m--){
        int x=wrd(),y=wrd();
        a[x]+=y;
    }
    A[0]=a[0];
    for(int i=1;i<=n;++i) A[i]=A[i-1]+a[i],B[i]=B[i-1]+i*a[i];

    sg1[0].b=sg2[0].b=inf;

    for(int i=0;i<n;++i){
        dp[i][1]=i*A[i]-B[i];
        dp[i][2]=qry(0,n,1,i,0)+i*A[i]-B[i];
        dp[i][3]=qry(0,n,1,i,1)+i*A[i]-B[i];

        sg1[i]={-A[i],dp[i][1]+B[i]};
        sg2[i]={-A[i],dp[i][2]+B[i]};
        modify(0,n,1,i,0),modify(0,n,1,i,1);

        ans=min(ans,dp[i][3]+n*(A[n]-A[i])-B[n]+B[i]);
    }
    return printf("%lld",ans),0;
}