P13767 [CERC 2021] Fishing

在亚得里亚海沿岸有一个小村庄。渔民们将大海划分为 $N \times M$ 的网格，第一行紧邻海岸，最后一行最远离海岸。他们追踪鱼群和其他漂浮物的移动。大海大部分区域是空的，但有 $K$ 个感兴趣的网格单元。每个单元的位置用第 $R_i$ 行和第 $C_i$ 列表示。渔民们估计在第 $i$ 个单元捕鱼的收益为 $V_i$。注意，如果该区域主要被不受欢迎的物品占据，$V_i$ 可能为零或负数。其他所有单元的价值均视为 0。 每天，当地议会会批准一个矩形捕鱼区域，包含从第 $X$ 列到第 $Y$ 列，并从海岸向海延伸 $H$ 行。为了在选定区域捕鱼，渔民们会准备一张长度恰好为 $H$ 的渔网。虽然渔网长度固定，但宽度 $W$ 可以任意选择，且不超过 $Y - X + 1$。根据他们对海域的了解，他们会在批准的捕鱼区域内选择一个位置下网，以最大化捕获量，即渔网覆盖的所有单元的价值之和。 渔民们希望每天都选择最优的捕鱼位置。请编写程序，针对接下来 $Q$ 天批准的捕鱼区域，计算他们能获得的最大收益。你可以假设每个单元的价值是恒定的，不会因前几天捕鱼而减少。

第一行包含行数 $N$、列数 $M$ ，第二行包含非空单元数 $K$。接下来的 $K$ 行，每行包含 $R_i$、$C_i$ 和 $V_i$，用空格分隔。行号从 1 到 $N$，列号从 1 到 $M$。所有 $V_i$ 均为整数。 下一行包含查询数 $Q$。第 $j$ 个查询由三个整数 $H'_j$、$X'_j$ 和 $Y'_j$ 描述。为保证按顺序回答查询，查询以编码形式给出。实际查询可按如下方式计算： $$ \begin{aligned} H_j &= H'_j \oplus A_{j-3}, \\ X_j &= X'_j \oplus A_{j-2}, \\ Y_j &= Y'_j \oplus A_{j-1}, \end{aligned} $$ 其中 $A_j$ 表示第 $j$ 个查询的答案（若 $j \leq 0$，则为 0），$\oplus$ 表示按位异或操作。你的程序应找到覆盖前 $H_j$ 行、列区间为 $X_j$ 到 $Y_j$ 的区域内，渔民能获得的最大收益。

对于每个查询，输出一行，表示最大捕获收益。注意，渔民也可以选择不下网，此时收益为 0。

### 说明 解码后的查询列表： ``` 5 1 5 10 1 7 7 6 6 8 2 6 4 1 6 3 1 2 ``` ### 输入范围 - $1 \leq N, M, K, Q \leq 300\,000$ - $|V_i| \leq 1000$ 由 ChatGPT 4.1 翻译