尼罗河题解

· · 题解

题目传送门

刚看到这题的时候还是紫，过了二十分钟降蓝了。

考虑 O(nq) 做法。我们把所有货物按照 w 排序，令 f_i 为前 i 个全部运走所需的最小代价。

注意到一个性质：如果把所有两两配对的货物视为一条线段，在最优情况下这些线段一定能够不相交。假设两两有相交，将四个点中左边两个和右边两个连一起显然合法且等价。

注意到另一个性质：如果把所有两两配对的货物视为一条线段，在最优情况下这些线段长度不会超过 3。也就是说一个货物最多只需要考虑前两个货物。假设与前面第三个货物配对，将这个点以及前三个点左边两个连一起显然合法且等价。

于是递推式:

f_{i-1}+a_i & w_i-w_{i-1}>d \\ \min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i) & w_i-w_{i-1}\le d\\ \min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i,f_{i-3}+b_{i-2}+a_{i-1}+b_i) & w_i-w_{i-2}\le d \\ \end{cases}

考虑优化。注意到询问可以离线出来，按照 d 排序。

这样转移的限制越来越宽，每个位置的转移式子也会变化。但是这些变化的总数是 O(n) 级别的。

考虑维护每个式子变化的时间。把每个 i 分别按照 w_i-w_{i-1} 和 w_i-w_{i-2} 从小到大排序，能够快速求出对于某个询问哪些式子会改变。

我们把转移抽象成广义矩阵乘法。其中把乘法操作变为加法，加法操作变为取 \min。即：

matrix operator * (matrix a,matrix b){
    matrix ans;
    ans.init1(3,3);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]);
            }
        }
    }
    return ans;
}

因为需要考虑前两个位置，矩阵边长为 3。

三个转移对应的矩阵乘分别为：

\begin{bmatrix} a_i & +\infty & +\infty \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix} \begin{bmatrix} a_i & b_i+b_{i-1} & +\infty \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix} \begin{bmatrix} a_i & b_i+b_{i-1} & b_i+a_{i-1}+b_{i-2} \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix}

能够证明这种运算具有结合率。

线段树维护每个式子，单点修改 O(n) 次，复杂度 O(n \log n)。最后根节点就是答案。

细节见代码部分。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
struct matrix{
    int n,m;
    long long a[3][3];
    inline void init0(int x,int y){
        n=x,m=y;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) a[i][j]=0;
        return;
    }
    inline void init1(int x,int y){
        n=x,m=y;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++){
            a[i][j]=1e18;
        }
        return;
    }
    inline void print(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
};
matrix operator * (matrix a,matrix b){
    matrix ans;
    ans.init1(3,3);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]);
            }
        }
    }
    return ans;
}
struct node{
    int w,a,b;
}p[N];
struct ask{
    int id,d;
}e[N];
int ans[N];
int n,q;
vector <long long> res;
long long w[N],a[N],b[N];
bool cmp(ask a,ask b){
    return a.d<b.d;
}
matrix tree[N*4];
inline void push_up(int x){
    tree[x]=tree[x*2+1]*tree[x*2];
}
int f1,f2;
inline void build(int l,int r,int x){
    if(l==r){
        tree[x].init1(3,3);
        tree[x].a[0][0]=a[l];
        tree[x].a[1][0]=0;
        tree[x].a[2][1]=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    push_up(x);
    return;
}
matrix d;
inline void updata(int l,int r,int id,int x){
    if(l>id || r<id) return;
    if(l>=id && r<=id){
        if(l==2){
            tree[x].a[0][0]=f2;
            tree[x].a[1][0]=f1;
            tree[x].a[2][0]=0;
            return;
        }
        tree[x]=d; 
        return;
    }
    int mid=l+r>>1;
    if(mid>=id) updata(l,mid,id,x*2);
    if(mid+1<=id) updata(mid+1,r,id,x*2+1);
    if(l==1 && r==2) tree[x]=tree[x*2+1]; else push_up(x);
    return;
}
bool cmp0(node a,node b){
    return a.w<b.w;
}
vector <pair <int,int> > v1,v2;
std::vector<long long> calculate_costs(
std::vector<signed> W, std::vector<signed> A, 
std::vector<signed> B, std::vector<signed> E){
    n=W.size(),q=E.size();
    for(int i=1;i<=n;i++) p[i].a=A[i-1],p[i].b=B[i-1],p[i].w=W[i-1];
    sort(p+1,p+1+n,cmp0);
    for(int i=2;i<=n;i++) v1.push_back({p[i].w-p[i-1].w,i});
    for(int i=3;i<=n;i++) v2.push_back({p[i].w-p[i-2].w,i});
    for(int i=1;i<=n;i++) a[i]=p[i].a,b[i]=p[i].b,w[i]=p[i].w;
    for(int i=1;i<=q;i++) e[i].d=E[i-1],e[i].id=i;
    sort(e+1,e+1+q,cmp);
    sort(v1.begin(),v1.end()),sort(v2.begin(),v2.end());
    build(1,n,1);
    int x=0,y=0;
    for(int i=1;i<=q;i++){
        f1=a[1];
        if(w[2]-w[1]<=e[i].d) f2=b[1]+b[2];
        else f2=a[1]+a[2];
        updata(1,n,2,1);
        d.init1(3,3);
        d.a[1][0]=0;
        d.a[2][1]=0;
        while(x<n-1 && v1[x].first<=e[i].d){
            int j=v1[x].second;
            d.a[0][0]=a[j];
            d.a[0][1]=b[j]+b[j-1];
            updata(1,n,v1[x].second,1),++x;
        } 
        while(y<n-1 && v2[y].first<=e[i].d){
            int j=v2[y].second;
            d.a[0][0]=a[j];
            d.a[0][1]=b[j]+b[j-1];
            d.a[0][2]=b[j]+b[j-2]+a[j-1];
            updata(1,n,v2[y].second,1),++y;
        }
        ans[e[i].id]=tree[1].a[0][0];
    }
    for(int i=1;i<=q;i++) res.push_back(ans[i]);
    return res;
}