[数据结构与算法]Codeforces 1649F 线段树

题意

传送门 Codeforces 1649F Serious Business

题解

枚举第一行的最右侧位置和最后一行的最左侧位置，将表达式分离变量可以得到
max ? 0 ≤ i ≤ j < n { f i + g i + c o s t ( i , j ) } \max\limits_{0\leq i\leq j<n}\{f_i+g_i+cost(i,j)\} 0≤i≤j<nmax?{fi?+gi?+cost(i,j)} 其中，$sum$ 为前缀和，$cost(i,j)$ 为打通第二行 $[i,j]$ 的花费，且 $$f_i=sum[0][i+1]?sum[1][i],g_i=sum[1][i+1]+sum[2][n]?sum[2][i]$$ 直接处理 $cost(i,j)$ 较为困难，考虑将区间按照右界升序排序，依次枚举 $q$ 个区间为所使用的最右侧区间。那么线段树维护 max ? 0 ≤ i ≤ j < n { f i ′ + g i } \max\limits_{0\leq i\leq j<n}\{f^{\prime}_i+g_i\} 0≤i≤j<nmax?{fi′?+gi?} 即可，其中 $f_i^{\prime }$ 代表 $(0,0)?(1,i)$ 所需的花费，其中可能包含零个或多个区间，可以在查询的过程中更新。

max ? 0 ≤ i ≤ j < n { f i ′ + g i } \max\limits_{0\leq i\leq j<n}\{f^{\prime}_i+g_i\} 0≤i≤j<nmax?{fi′?+gi?} 有两种维护思路，一种是查询时将 $f,g$ 最大值递归至左右子区间进行查询；第二种考虑分治，即满足条件的 $f,j$ 要么出现在左子区间或右子区间，要么由左子区间的最大 $f$ 与右子区间的最大 $g$ 构成。

总时间复杂度 $O(q\log n)$。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 5E5 + 5, SZ = 1 << 20;
struct seg
{
    int l, r, k;
    bool operator<(const seg &o) { return r < o.r; }
} ss[MAXN];
int N, Q, A[3][MAXN];
ll f[MAXN], g[MAXN], sum[3][MAXN];
struct node
{
#define f(v) tree[v].f
#define g(v) tree[v].g
#define mx(v) tree[v].mx
    ll f, g, mx;
    node operator+(node o)
    {
        node res;
        res.f = max(f, o.f), res.g = max(g, o.g);
        res.mx = max(max(mx, o.mx), f + o.g);
        return res;
    }
} tree[SZ];

void init(int k = 0, int l = 0, int r = N)
{
    if (r - l == 1)
    {
        f(k) = f[l], g(k) = g[l];
        mx(k) = f(k) + g(k);
        return;
    }
    int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
    init(chl, l, m), init(chr, m, r);
    tree[k] = tree[chl] + tree[chr];
}

void change(int a, int b, ll x, int k = 0, int l = 0, int r = N)
{
    if (r <= a || b <= l)
        return;
    if (a <= l && r <= b)
    {
        f(k) = max(f(k), x);
        mx(k) = f(k) + g(k);
        return;
    }
    int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
    change(a, b, x, chl, l, m), change(a, b, x, chr, m, r);
    tree[k] = tree[chl] + tree[chr];
}

node ask(int a, int b, int k = 0, int l = 0, int r = N)
{
    if (a <= l && r <= b)
        return tree[k];
    int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
    if (b <= m)
        return ask(a, b, chl, l, m);
    if (m <= a)
        return ask(a, b, chr, m, r);
    return ask(a, b, chl, l, m) + ask(a, b, chr, m, r);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> Q;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < N; ++j)
            cin >> A[i][j], sum[i][j + 1] = sum[i][j] + A[i][j];
    for (int i = 0; i < N; ++i)
        f[i] = sum[0][i + 1] - sum[1][i], g[i] = sum[1][i + 1] + sum[2][N] - sum[2][i];
    for (int i = 0; i < Q; ++i)
    {
        auto &s = ss[i];
        cin >> s.l >> s.r >> s.k;
        --s.l;
    }
    sort(ss, ss + Q);
    init();
    ll res = LLONG_MIN;
    for (int i = 0; i < Q; ++i)
    {
        auto &s = ss[i];
        auto v = ask(s.l, s.r);
        res = max(res, v.mx - s.k);
        if (s.r < N)
            change(s.r, s.r + 1, v.f - s.k);
    }
    cout << res << '\n';
    return 0;
}