題意

給定一個 \(3\times n\) 的網格，每個格子 \((i,j)\) 內有一個數 \(a_{i,j}\)。一個人初始分數為 \(0\)，在位置 \((1,1)\) 處，每次可以向右或向下走一格，目標是到達 \((3,n)\)。當走到格子 \((i,j)\) 時，這個人的分數會增加 \(a_{i,j}\)。

起初，只有第一、三行的格子是可用的。現在給出了 \(q\) 個區間 \([l_i,r_i]\) 和 \(k_i\)，表示這個人可以減少 \(k_i\) 的得分讓第二行第 \(l_i\) 到 \(r_i\) 個格子變得可用。求達成目標的最大得分。\(1\leq n,q\leq 5\times 10^5\)，\(-10^9\leq a_{i,j}\leq 10^9\)，\(1\leq k_i\leq 10^9\)。

題解

下文中令 \(s_{i,j}=\sum_{k=1}^ja_{i,k}\)。

考慮 DP。令 \(f_i\) 表示從 \((1,1)\) 走到 \((2,i)\)，欽定 \(i\) 是某個區間的右端點的最大得分。我們從小到大枚舉 \(i\)，遍歷所有右端點為 \(i\) 的區間 \([l,i]\)，考慮其轉移：

• 從前面某個區間的右端點對應的 \((2,j)\) 向右走到 \((2,i)\)：
  \[f_i\leftarrow \max_{l-1\leq j\leq i-1}\{f_j-s_{2,j}\}+s_{2,i}-k \]

• 從 \((1,j)\) 向下走到區間內的 \((2,j)\)，然后向右走到 \((2,i)\)
  \[f_i\leftarrow \max_{l\leq j\leq i}\{s_{1,j}-s_{2,j-1}\}+s_{2,i}-k \]

后者顯然是 RMQ，可以使用 ST 表維護。前者也可以用線段樹維護 \(f_j-s_{2,j}\) 的區間 \(\max\)，不過我們注意到 \(>i\) 的部分是沒有有效值的，所以實際上是后綴詢問，可以使用 BIT 維護。

考慮如何統計答案。問題在于，從第二行走到第三行的拐點，不一定在某個區間的右端點上。但是我們可以發現，在第二行解鎖的區間中，最多只有一個區間的右端點沒有被走到。因為如果有多個沒走滿的區間，我們顯然可以刪掉左端點最大的那個。于是我們枚舉沒走滿的區間 \([l,r]\)，做和前面類似的分類討論：

• 從前面某個區間的右端點對應的 \((2,i)\) 走到 \((2,j)\)：
  \[\begin{align*} ans&\leftarrow \max_{l-1\leq i\leq j\leq r}\{f_i+s_{2,j}-s_{2,i}+s_{3,n}-s_{3,j-1}\}\\ &=\max_{l-1\leq i\leq j\leq r}\{(f_i-s_{2,i})+(s_{2,j}-s_{3,j-1})\}+s_{3,n} \end{align*} \]

• 從 \((1,i)\) 向下走到 \((2,i)\)，再向右走到 \((2,j)\)：
  \[\begin{align*} ans&\leftarrow \max_{l\leq i\leq j\leq r}\{s_{1,i}+s_{2,j}-s_{2,i-1}+s_{3,n}-s_{3,j-1}\}\\ &=\max_{l-1\leq i\leq j\leq r}\{(s_{1,i}-s_{2,i-1})+(s_{2,j}-s_{3,j-1})\}+s_{3,n} \end{align*} \]

兩者都是形如區間查詢 \(\max_{l\leq i\leq j\leq r}\{A(i)+B(j)\}\) 的形式，可以使用線段樹維護，在節點上維護區間的 \(A,B\) 最大值和 \(\max_{l\leq i\leq j\leq r}\{A(i)+B(j)\}\) 即可。

時間復雜度 \(\mathcal{O}((n+q)\log{n})\)。

代碼

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e5 + 5;
const ll INF = 1e18;

namespace IO {
	const int S = 1 << 24, lm = 1 << 23;
	char bi[S + 5], *p1 = bi, *p2 = bi, ch;
	int s;
	#define gc() (p1 == p2 && (p2 = (p1 = bi) + fread(bi, 1, 1 << 23, stdin), p1 == p2) ? EOF : *p1++)
	inline ll rd() {
		s = 1; char ch;
		while (ch = gc(), (ch < '0')) if (ch == '-') s = -1;
		ll x = ch ^ 48;
		while (ch = gc(), (ch >= '0')) x = (x << 3) + (x << 1) + (ch ^ 48);
		return s == 1 ? x : -x;
	}
}
using IO::rd;

template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }

int n, m, a[3][N];
ll val1[N], val2[N];
ll ans = -INF, pre[3][N], f[N];
struct Range { int l, r, k; } rg[N];
basic_string<Range> vec[N];

struct BIT {
	ll c[N];
	inline void init() { fill(c + 1, c + n + 1, -INF); }
	inline ll query(int x) {
		ll res = -INF;
		for (; x <= n; x += lowbit(x)) chk_max(res, c[x]);
		return res;
	}
	inline void upd(int x, ll v) { for (; x; x -= lowbit(x)) chk_max(c[x], v); }
} ft1, ft2;
struct SegTree2 {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
	struct Node {
		ll mx1, mx2, dat;
		Node() : mx1(-INF), mx2(-INF), dat(-INF) {}
		Node(ll mx1, ll mx2, ll dat) : mx1(mx1), mx2(mx2), dat(dat) {}
		Node operator+(const Node &x) const { return {max(mx1, x.mx1), max(mx2, x.mx2), max({dat, x.dat, mx1 + x.mx2})}; }
	} nodes[N << 2];
	inline void push_up(int p) { nodes[p] = nodes[ls(p)] + nodes[rs(p)]; }
	inline void build(int p, int l, int r) {
		if (l == r) return nodes[p] = {val1[l], val2[l], val1[l] + val2[l]}, void();
		int mid = l + r >> 1;
		build(ls(p), l, mid), build(rs(p), mid + 1, r);
		push_up(p);
	}
	inline Node query(int p, int l, int r, int x, int y) {
		if (x <= l && y >= r) return nodes[p];
		int mid = l + r >> 1; Node res;
		if (x <= mid) res = query(ls(p), l, mid, x, y);
		if (y > mid) res = res + query(rs(p), mid + 1, r, x, y);
		return res;
	}
#undef ls
#undef rs
} sgt3;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	n = rd(), m = rd();
	for (int i = 0; i < 3; ++i) for (int j = 1; j <= n; ++j) a[i][j] = rd(), pre[i][j] = pre[i][j - 1] + a[i][j];
	for (int i = 1, l, r, k; i <= m; ++i) l = rd(), r = rd(), k = rd(), vec[r] += rg[i] = {l, r, k};
	fill(f + 1, f + n + 1, -INF), ft1.init(), ft2.init();
	for (int i = 1; i <= n; ++i) {
		ft2.upd(i, pre[0][i] - pre[1][i - 1]);
		for (Range it : vec[i]) {
			int l = it.l, k = it.k;
			if (i > 1) chk_max(f[i], ft1.query(max(l - 1, 1)) + pre[1][i] - k);
			chk_max(f[i], ft2.query(l) + pre[1][i] - k);
		}
		ft1.upd(i, f[i] - pre[1][i]);
	}
	for (int i = 1; i <= n; ++i) val1[i] = f[i] - pre[1][i], val2[i] = pre[1][i] - pre[2][i - 1];
	sgt3.build(1, 1, n);
	for (int i = 1; i <= m; ++i) chk_max(ans, sgt3.query(1, 1, n, max(rg[i].l - 1, 1), rg[i].r).dat + pre[2][n] - rg[i].k);
	for (int i = 1; i <= n; ++i) val1[i] = pre[0][i] - pre[1][i - 1];
	sgt3.build(1, 1, n);
	for (int i = 1; i <= m; ++i) chk_max(ans, sgt3.query(1, 1, n, rg[i].l, rg[i].r).dat + pre[2][n] - rg[i].k);
	cout << ans;
	return 0;
}