P13544 [OOI 2022] Serious Business

CF1648D

Dima 参加了好友 Peter 举办的节目《Peter 帮兄弟找工作》。在这个节目中，Dima 需要穿越一个 $3 \times n$ 的矩形场地，场地共有 $3$ 行 $n$ 列。每行的格子从左到右编号为 $1$ 到 $n$。 每个格子 $(i, j)$ 内有一个整数 $a_{i, j}$。Dima 的初始分数为 $0$，每当他经过某个格子 $(i, j)$，分数会增加 $a_{i, j}$（分数可能为负）。 起初，第一行和第三行的所有格子都是可用的，第二行所有格子都是不可用的。但 Peter 为 Dima 提供了 $q$ 个特殊帮助，第 $i$ 个特殊帮助可以将第二行的第 $l_i$ 列到第 $r_i$ 列的格子标记为可用，但每次使用该特殊帮助，Dima 的分数会减少 $k_i$。Dima 可以任意多次使用这些特殊帮助，同一格子可被多次解锁。 Dima 从第一行第一列的格子 $(1, 1)$ 出发，目标是到达第三行最后一列的格子 $(3, n)$。每次他可以向下走到下一行，或者向右走到下一列（即行号或列号加 $1$），因此总共需要 $n+1$ 步，其中 $n-1$ 步为向右，$2$ 步为向下。 Peter 承诺根据 Dima 的最终分数付费，最终分数为经过的所有格子的分数之和减去使用所有特殊帮助的总花费。请你帮助 Dima 最大化他的最终分数。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 500\,000$），分别表示场地的列数和特殊帮助的数量。 接下来的三行，每行 $n$ 个整数 $a_{i1}, a_{i2}, \ldots, a_{in}$（$-10^9 \le a_{ij} \le 10^9$），表示场地每个格子的分数。 接下来 $q$ 行，每行三个整数 $l_i, r_i, k_i$（$1 \leq l_i \leq r_i \leq n$，$1 \leq k_i \leq 10^9$），表示第 $i$ 个特殊帮助可以将第二行 $l_i$ 到 $r_i$ 的格子解锁，且每次使用该帮助需要花费 $k_i$ 分数。

输出一个整数，表示 Dima 能获得的最大最终分数。

本题共 6 组测试点。只有通过某组所有测试点和所有必需的前置组，才能获得该组分数。**离线评测**表示该组的结果在比赛结束后才能看到。注意，有些分组不要求通过样例测试点。 | 组别 | 分值 | $n$ | $q$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:---:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | 样例测试点 | | 1 | 10 | -- | $q=1$ | -- | | | | 2 | 16 | $n \leq 500$ | $q \leq 500$ | 0 | | | 3 | 14 | $n \leq 2\,000$ | $q \leq 5\,000$ | 0,2 | | | 4 | 17 | -- | -- | -- | -- | 所有 $k_i$ 相等 | | 5 | 21 | $n \leq 100\,000$ | $q \leq 100\,000$ | 0,2,3 | | | 6 | 22 | -- | -- | -- | 0--5 | **离线评测** |