题解 CF115E 【Linear Kingdom Races】

王鲲鹏 · 2020-07-15 11:40:16 · 题解

Update 2020-07-15 晚:
同学zly指出了一些问题，比较严重，更正一次。在公式中忽略了当i=j时l=r=i的赛事的收益。

这是一道 线段树优化DP 的模板题。

我跟第一篇题解的思路相反，定义 f[i][j] 表示考虑到第i个道路，[j,i]全都选择的最大收益。Ans表示考虑到i时累计的最大收益。

考虑如何从 f[i-1][?] 转移到 f[i][j] 。 对于 j < i ，新增了道路i的代价 cost_i，和右端点 r=i ，并且能被区间[j,i]覆盖的赛事的收益的和。

对于 j=i，

如何优化到一个比较好的复杂度呢？

可以发现每次新考虑一个道路时， 区间[1,i]都相当于在f[i-1][\cdots]的基础上减去同一个值cost_i； 对每个右端点为i 的比赛，在这个时候有贡献，区间 [1,l_b] 加上 p_b（在f[i-1][\cdots]的基础上），对f[i][i]，可以看做赋值Ans（区间减时减去cost_i）。

如果考虑滚动数组，发现其实上述转移是区间加， 维护Ans的过程是区间求最值。

于是考虑线段树。

最后一个小问题，如何维护右端点在i的所有赛事呢？我这里有两种方法，一个是用链表（就是邻接表），一个是按右端点排序后扫描，大家应该都会吧。

代码

#include <cstdio>
typedef long long ll;
const int maxn = 200003;
int read() {
    int x = 0, c = getchar();
    while (c < '0' && c > '9') c = getchar();
    while ('0' <= c && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x;
}
int n = 0, m = 0;
int head[maxn], left[maxn], nxt[maxn], cnt = 0;
ll p[maxn], w[maxn];
void insert(int R, int L,int v) {
    nxt[++cnt] = head[R];
    head[R] = cnt;
    left[cnt] = L;
    p[cnt] = v;
}
ll ma[maxn<<2], lazy[maxn<<2];
inline ll max(ll a, ll b) { return a<b?b:a; }
inline void pushDown(int p) {
    ma[p << 1] += lazy[p];    
    ma[p << 1 | 1] += lazy[p];
    lazy[p << 1] += lazy[p];
    lazy[p << 1 | 1] += lazy[p];
    lazy[p] = 0;
}
inline void pushUp(int p) {
    ma[p] = max(ma[p<<1], ma[p<<1|1]);
}
void plus(int p,int L,int R,int l,int r, ll v) {
    if(l <= L && R <= r) {
        ma[p]+=v;
        lazy[p]+=v;
        return;
    }
    pushDown(p);
    int mid = (L+R)>>1;
    if(l <=mid) plus(p<<1,L,mid, l,r,v);
    if(r>mid) plus(p<<1|1,mid+1,R,l,r,v);
    pushUp(p);
}
int main() {
    n = read(); m = read();
    for (int i = 1;i<=n;++i) w[i] = read();
    int L = 0, R = 0, P = 0;
    for(int i=1;i<=m;++i) {
        L=read(); R=read(); P=read();
        insert(R,L,P);
    }
    ll ans = 0;
    for(int i = 1;i<=n;++i) {
        plus(1,1,n,i,i,ans);
        plus(1,1,n,1,i,-w[i]);
        for(int j = head[i];j;j=nxt[j])
            plus(1,1,n,1,left[j], p[j]);
        ans = max(ans,ma[1]);
    }
    printf("%lld", ans);
    return 0;
}