题解 CF115E 【Linear Kingdom Races】

· · 题解

看完题后，你的第一个想法可能是考虑每场比赛是否进行，并计算相应的路费。
但是，如果两次比赛的路线重合，路费就只用支付一次。由此就产生了后效性，对我们的DP造成了困难。

那么，我们可以反过来想：考虑每条路是否支付路费（修路），并算出所有可以进行的比赛赚到的钱。
设 f[i] 表示前 i 条路中修复若干条路后可以赚到的最多的钱。
转移方程：

我们考虑用线段树来优化，第 j 个位置 (0 \le j \le n) 的 c[j] 储存 f[j]+\operatorname{val}(j+1,i)-\operatorname{cost}(j+1,i)
每次枚举到一个新的 i 时：

  1. 将 c[0\dots i-1] 减去 a[i]（修路的价钱），因为都要多修一条路。
  2. 对于每个右端点 r=i 的比赛 (l,r,v)，将 c[0\dots l-1] 都加上 v。因为在这些状态中，[l,r] 区间的路都修好了（可以进行比赛）。
  3. 更新当前状态：f[i]=\max(f[i-1],\max\limits_{0\le j < i}\{c[j]\})。
  4. 最后，更新线段树中的 c[i]。

总时间复杂度\operatorname{O}(n\log n)。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const long long Maxn=200000+10,inf=(1ll<<60);
const long long Maxm=Maxn<<2;
struct node{
    long long p,v;
    node(long long x,long long y)
    {
        p=x,v=y;
    }
};
long long maxv[Maxm],add[Maxm];
long long a[Maxn],f[Maxn];
vector <node> c[Maxn];
long long n,m;
inline long long read()
{
    long long s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
inline void check(long long &x,long long y)
{
    if(y>x)x=y;
}
inline void push_up(long long k)
{
    maxv[k]=max(maxv[k<<1],maxv[k<<1|1]);
}
inline void upd(long long k,long long v)
{
    maxv[k]+=v;
    add[k]+=v;
}
inline void push_down(long long k)
{
    if(!add[k])return;
    upd(k<<1,add[k]);
    upd(k<<1|1,add[k]);
    add[k]=0;
}
void modify(long long k,long long l,long long r,long long x,long long y,long long v)
{
    if(x<=l && r<=y)return upd(k,v);
    push_down(k);
    long long mid=(l+r)>>1;
    if(x<=mid)modify(k<<1,l,mid,x,y,v);
    if(mid<y)modify(k<<1|1,mid+1,r,x,y,v);
    push_up(k);
}
long long query(long long k,long long l,long long r,long long x,long long y)
{
    if(x<=l && r<=y)return maxv[k];
    push_down(k);
    long long mid=(l+r)>>1,ret=-inf;
    if(x<=mid)ret=query(k<<1,l,mid,x,y);
    if(mid<y)check(ret,query(k<<1|1,mid+1,r,x,y));
    return ret;
}
void modify_val(long long k,long long l,long long r,long long pos,long long v)
{
    if(l==r)
    {
        add[k]=0,maxv[k]=v;
        return;
    }
    push_down(k);
    long long mid=(l+r)>>1;
    if(pos<=mid)modify_val(k<<1,l,mid,pos,v);
    else modify_val(k<<1|1,mid+1,r,pos,v);
    push_up(k);
}
int main()
{
    n=read(),m=read();
    for(long long i=1;i<=n;++i)
    a[i]=read();
    while(m--)
    {
        long long x=read(),y=read(),v=read();
        c[y].push_back(node(x,v));
    }
    for(long long i=1;i<=n;++i)
    {
        modify(1,0,n,0,i-1,-a[i]);
        for(long long j=0;j<c[i].size();++j)
        {
            long long p=c[i][j].p,v=c[i][j].v;
            modify(1,0,n,0,p-1,v);
        }
        f[i]=max(query(1,0,n,0,i-1),f[i-1]);
        modify_val(1,0,n,i,f[i]);
    }
    printf("%lld\n",f[n]);
    return 0;
}