题解：P16319 [ICPC 2023 Jinan R] 铁路环游

· · 题解

题意简述

有 n 条依次排列的铁路。车票 (l,r,v) 会在第 l+1 至第 r 条铁路全部建成时贡献 v 分。

对每个 1\le k\le n，求恰好建造 k 条铁路时的最大得分。

解题思路

把没有建造的铁路称为断点。若恰好建造 k 条铁路，就需要放置 t=n-k 个断点。

从左到右处理铁路。设 f_{t,i} 表示一种状态的最大得分。该状态在前 i 条铁路中有 t 个断点，并且第 i 条铁路已经建造。设 g_{t,i} 表示相同范围内的最优值，但要求第 i 条铁路是断点。

若把第 i 条铁路设为断点，所有右端点为 i 的车票都不能得分。前 i-1 条铁路的最后一条既可以建造，也可以是断点。因此：

g_{t,i}=\max(f_{t-1,i-1},g_{t-1,i-1})

下面考虑第 i 条铁路已经建造的情况。设它左侧最后一个断点为 p，那么第 p+1 至第 i 条铁路全部建成。记 w_{p+1,i} 为完全包含在这段连续铁路内的车票权值和，转移为：

f_{t,i}=\max_{t\le p<i}\left\{g_{t,p}+w_{p+1,i}\right\}

固定断点数 t，按照右端点递增枚举 i。对每个已经出现的最后断点位置 p，维护当前候选值：

h_p=g_{t,p}+w_{p+1,i}

处理右端点为 i 的车票 (l,i,v)。它在最后断点满足 p\le l 时才能得分。因此，要给候选序列的前缀 h_t,h_{t+1},\dots,h_l 全部加上 v。处理完这些车票后，在序列末尾插入新候选 g_{t,i}，再查询全局最大值。

问题归结为维护一个动态序列，操作只有三种：

只保留序列从左到右出现的严格前缀最大值。它们形成严格递增的记录点。普通位置只需归属于它左侧最近的记录点，因为它不可能单独决定全局最大值。

在相邻记录点之间保存最大值之差。设位置 p 所属记录点为 x。给截至 p 的前缀加 v 后，更新范围内的最大值就是 x 的值加 v。更早的记录点同样增加 v，仍不会超过它。

若 x 与下一个记录点的差值大于 v，只需将该差值减去 v。否则，x 会追上下一个记录点，两段便可合并。减去被消耗的差值后，继续尝试合并后面的记录点。若一直走到最后，尚未消耗的增量会直接增加全局最大值。

用并查集维护每个原位置当前所属的记录点，并用链表连接相邻记录点。合并时把右侧记录点并入左侧记录点。之后从任何已合并位置出发，都能直接跳到仍然存在的记录点。

在固定的 t 中，每次插入至多建立一个新记录点，每个记录点至多被合并一次。因此，全部前缀加操作的额外合并次数是线性的。每轮只重置记录点数量和最大值；节点内容会在下一次插入时覆盖，不需要清空整个数组。

当没有断点时，前 i 条铁路全部建成。此时 f_{0,i} 是右端点不超过 i 的全部车票权值和。依次计算 t=1,2,\dots,n-1，便能得到每个建造数量的答案。

时间复杂度为 O(n(n+m)\alpha(n))，空间复杂度为 O(n+m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=10005;
struct Seq
{
    int fa[N],to[N],id[N],cnt;
    ll dif[N],mx;
    int find(int x)
    {
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
    void clear()
    {
        cnt=mx=0;
        fa[0]=to[0]=0;
    }
    void push(int p,ll v)
    {
        id[p]=++cnt;
        fa[cnt]=cnt;
        to[cnt]=0;
        dif[cnt]=0;
        if(v<=mx)
        {
            fa[cnt]=find(cnt-1);
            return;
        }
        dif[cnt]=v-mx;
        to[find(cnt-1)]=cnt;
        mx=v;
    }
    void add(int p,ll v)
    {
        int x=find(id[p]);
        while(to[x]&&dif[to[x]]<=v)
        {
            int y=to[x];
            v-=dif[y];
            fa[y]=x;
            to[x]=to[y];
        }
        if(to[x])dif[to[x]]-=v;
        else mx+=v;
    }
}q;
int n,m;
ll f[2][N],g[2][N],ans[N],sum[N];
vector<pair<int,ll>> seg[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)seg[i].clear();
        fill(sum,sum+n+1,0);
        fill(ans,ans+n+1,0);
        for(int i=1;i<=m;i++)
        {
            int l,r;
            ll v;
            cin>>l>>r>>v;
            seg[r].push_back({l,v});
            sum[r]+=v;
        }
        for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
        for(int i=1;i<=n;i++)
        {
            f[0][i]=sum[i];
            g[0][i]=sum[i-1];
        }
        ans[n]=sum[n];
        for(int i=1;i<n;i++)
        {
            int k=i,now=k&1,pre=now^1;
            fill(f[now],f[now]+n+1,0);
            fill(g[now],g[now]+n+1,0);
            q.clear();
            q.push(k,0);
            for(int j=k+1;j<=n;j++)
            {
                for(auto [l,v]:seg[j])
                {
                    if(l>=k)q.add(l,v);
                }
                g[now][j]=max(f[pre][j-1],g[pre][j-1]);
                q.push(j,g[now][j]);
                f[now][j]=q.mx;
            }
            ans[n-k]=max(f[now][n],g[now][n]);
        }
        for(int i=1;i<=n;i++)
        {
            if(i>1)cout<<' ';
            cout<<ans[i];
        }
        cout<<'\n';
    }
    return 0;
}