F. Serious Business

prob. ：有$3\times n$个格子，每个格子有一个权值，你要从左上走到右下，每一步只能往右或往下走，刚开始的时候第二行是封锁的状态，你有一些可选的操作去解锁第二行从$[L_i,R_i]$的格子，每种操作的代价分别是$k_i$, 问最大能获得的值是多少

ideas ：非常巧妙将三行的权值拆成两个函数

pref表示每行的前缀和

$s[i]=pref[0][i+1]-pref[1][i]$

$f[i]=pref[1][i+1]-pref[2][i]+pref[2][n]$

最终的答案变成$ma{x}_{0\le i<j<n}s[i]+f[j]-cost(i,j)$， cost指第二行解锁区间$[i,j]$的最小价值

// 在下面具体代码实现的时候s和f的+1-1可能和上述有些不同

直接用s+f更新答案是只解锁一个区间时候的答案，dp记录的是多个区间时候的答案（这里为了少转移只对每个操作的r端点更新值

dp是s-cost，对于每个操作$L_i,R_i$，用s和dp更新$dp[R]$, 对应的s是$[L,R]$区间的因为他还在第0行没有走下来，dp已经在第1行了，所以是由$[L-1,R-1]$转移的，（R这里不用算进去但可能算进去也没啥区别，因为-k之后肯定比本身小）

注意更新dp的时候要对区间排序

写死我了，我好菜啊，谢谢npy帮我debug，“有些人被迫参与全程”

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const ll N = 5e5 + 50;
const ll inf = 0x3f3f3f3f3f3f3f3f;struct node {ll l, r;ll s, f, sf;
};node tr[N << 2];ll s[N], f[N], dp[N];void pushup(ll u) {tr[u].s = max(tr[u << 1].s, tr[u << 1 | 1].s);tr[u].f = max(tr[u << 1].f, tr[u << 1 | 1].f);tr[u].sf = max(max(tr[u << 1].sf, tr[u << 1 | 1].sf), tr[u << 1].s + tr[u << 1 | 1].f);
}void build(ll u, ll l, ll r) {if (l == r) {tr[u] = {l, r, s[l], f[l], s[l] + f[l]};} else {tr[u] = {l, r, -inf, -inf, -inf};ll mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}
}void modify(ll u, ll l, ll r, ll s) {if (tr[u].l >= l && tr[u].r <= r) {tr[u].s = max(tr[u].s, s);tr[u].sf = tr[u].s + tr[u].f;return;}ll mid = (tr[u].l + tr[u].r) >> 1;if (l <= mid) modify(u << 1, l, r, s);if (r > mid) modify(u << 1 | 1, l, r, s);pushup(u);
}struct note {ll sf, s, f;
};note querySF(ll u, ll l, ll r) {if (tr[u].l >= l && tr[u].r <= r) {return {tr[u].sf, tr[u].s, tr[u].f};}ll mid = (tr[u].l + tr[u].r) >> 1;ll ansSF = -inf, ansS = -inf, ansF = -inf, ss = -inf, ff = -inf;if (l <= mid) {auto tmp = querySF(u << 1, l, r);ansSF = max(ansSF, tmp.sf);ansS = max(ansS, tmp.s);ansF = max(ansF, tmp.f);ss = max(ss, tmp.s);}if (r > mid) {auto tmp = querySF(u << 1 | 1, l, r);ansSF = max(ansSF, tmp.sf);ansS = max(ansS, tmp.s);ansF = max(ansF, tmp.f);ff = max(ff, tmp.f);}ansSF = max(ansSF, ss + ff);return {ansSF, ansS, ansF};
}ll a[5][N];
ll pref[5][N];struct seg {ll l, r;ll k;
};seg segs[N];signed main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);ll n, q;cin >> n >> q;bool checkflag = 0;for (ll i = 0; i < 3; ++i) {for (ll j = 1; j <= n; ++j) {cin >> a[i][j];if (a[i][j] > 0) checkflag = 1;pref[i][j] = pref[i][j - 1] + a[i][j];}}for (ll i = 1; i <= n; ++i) {s[i] = pref[0][i] - pref[1][i - 1];f[i] = pref[1][i] - pref[2][i - 1] + pref[2][n];}build(1, 1, n + 5);for (ll i = 0; i <= n; ++i) dp[i] = -inf; // init dpll ans = -inf;for (ll i = 1; i <= q; ++i) { // refresh dp by scin >> segs[i].l >> segs[i].r >> segs[i].k;ll l = segs[i].l, r = segs[i].r;ll k = segs[i].k;ans = max(ans, querySF(1, l, r).sf - k);ll tmp = querySF(1, l, r).s - k;dp[r] = max(tmp, dp[r]);}for (ll i = 0; i <= n; ++i) s[i] = dp[i];build(1, 1, n + 5);sort(segs + 1, segs + q + 1, [&](auto a, auto b) {return a.r < b.r;});for (ll i = 1; i <= q; ++i) { // refresh dp by dpll l = segs[i].l, r = segs[i].r;ll k = segs[i].k;ll tmp = querySF(1, (l - 1 == 0 ? l : l - 1), (r - 1 == 0 ? r : r - 1)).s - k;modify(1, r, r, tmp);ans = max(ans, querySF(1, (l - 1 == 0 ? l : l - 1), r).sf - k);}cout << ans << endl;return 0;
}