AT_jsc2025_final_e Politeness Matters

AtCoder 社与 BatCoder 社进行企业对抗赛。AtCoder 社有 $N$ 名员工，编号为 $1$ 到 $N$，第 $i$ 号员工的强度为 $A_i$，礼仪分为 $P_i$。BatCoder 社同样有 $N$ 名员工，编号 $1$ 到 $N$，第 $i$ 号员工的强度为 $B_i$。 企业对抗赛按照以下方式进行： - 首先，AtCoder 社宣布一个整数 $k$，满足 $0 \leq k \leq N$。 - 随后，两家公司各自选择强度最大的 $k$ 名员工作为出战成员（若强度相同，任意选取）。 - 这场企业对抗赛的得分为：$(\text{AtCoder 社成员强度之和}) - (\text{BatCoder 社成员强度之和})$。 接下来，AtCoder 社有 $Q$ 场招聘面试。第 $i$ 场面试时，出现一名候选人，强度为 $X_i$，礼仪分为 $Y_i$。在本次面试前，AtCoder 社员工的礼仪分最小值为 $z$。若 $Y_i < z$，则不录用该候选人；若 $Y_i > z$，则录用该候选人，并解雇礼仪分为 $z$ 的员工。题目保证所有员工及候选人的礼仪分都互不相同。 对于每个 $t=0,1,\ldots,Q$，即完成前 $t$ 场面试后，举行企业对抗赛。请你计算每个 $t$ 时最大可能的企业对抗赛得分。 此外，本题 $X_i,Y_i$ 的值只有在求出 $t=i-1$ 时的答案后，才能通过如下方式恢复。请参见输入格式。

输入从标准输入读取，格式如下： > $N$ $Q$ > $A_1$ $P_1$ > $A_2$ $P_2$ > ⋮ > $A_N$ $P_N$ > $B_1$ $B_2$ ⋯ $B_N$ > $X_1'$ $Y_1'$ > $X_2'$ $Y_2'$ > ⋮ > $X_Q'$ $Y_Q'$ 其中，$X_i',Y_i'$ 是 $X_i,Y_i$ 的加密值，满足 $0 \leq X_i',Y_i' < 2^{30}$。令 $ans_{i-1}$ 表示 $t=i-1$ 时的答案，则 $X_i,Y_i$ 可按如下方式恢复： - $X_i = X_i' \oplus (ans_{i-1} \bmod 2^{30})$ - $Y_i = Y_i' \oplus (ans_{i-1} \bmod 2^{30})$ 其中，$\oplus$ 表示按位异或运算。

输出 $Q+1$ 行。第 $i$ 行输出 $t=i-1$ 时的答案。

### 样例解释 1 - $t=0$：AtCoder 社选择 $k=3$ 最优。AtCoder 社成员强度之和为 $4+3+1=8$，BatCoder 社为 $3+3+0=6$，得分为 $8-6=2$。 - 第 $1$ 次面试：$(X_i, Y_i) = (1, 3)$。AtCoder 社解雇强度 $3$、礼仪分 $0$ 的员工，录用强度 $1$、礼仪分 $3$ 的新人。 - $t=1$：AtCoder 社选择 $k=1$ 最优，强度为 $4$，BatCoder 社为 $3$，得分 $4-3=1$。 ### 数据范围 - $1 \leq N \leq 250000$ - $1 \leq Q \leq 250000$ - $0 \leq A_i, B_i, P_i, X_i, Y_i < 2^{30}$ - $P_1,\ldots,P_N, Y_1,\ldots,Y_Q$ 均互不相同 - 所有输入均为整数 由 ChatGPT 5 翻译