分数: 550 点
问题陈述
在AtCoder Ranch,马儿正在洗澡。有些马会事后清理干净,而另一些则留下烂摊子。
有 N 马,编号 1 to N。马 i (1 \leq i \leq N)有一个 心情 A_i 和 整洁 B_i (其中 B_i is 1 or 2).
晚上, N 每匹马洗澡一次。让 p_j 是沐浴在水中的马的编号 j第回合(1 \leq j \leq N)。的 满意 马 p_j 给出如下:
- If j \geq 2,马心情的产物 p_j 和马的整洁 p_{j-1}.
- If j = 1,马的心情 p_j.
你将得到 Q 查询,每天一次 Q 天。按顺序处理它们。查询为 k- 第天 (1 \leq k \leq Q)如下:
- 改变马的心情 W_k to X_k 及其整洁度 Y_k (其中 Y_k is 1 or 2)。然后,找到最大可能的总满意度 N 那天晚上,如果你能决定马匹洗澡的顺序 N 马任意洗澡。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
- B_i is 1 or 2. (1 \leq i \leq N)
- 1 \leq W_k \leq N (1 \leq k \leq Q)
- 1 \leq X_k \leq 10^6 (1 \leq k \leq Q)
- Y_k is 1 or 2. (1 \leq k \leq Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 B_1 \vdots A_N B_N W_1 X_1 Y_1 \vdots W_Q X_Q Y_Q
输出
输出 Q 行。的 k- 第行 (1 \leq k \leq Q)应包含查询的答案 k- 第一天。
示例输入 1
4 4 1 2 10 1 3 1 7 2 2 7 1 1 3 1 2 2 1 3 1000000 2
示例输出 1
32 27 18 2000015
第一天查询,马匹是否按顺序洗澡 3,1,4,2,每匹马的满意度如下:
- 马 3的满意度是 3
- 马 1的满意度是 1 \times 1 = 1
- 马 4的满意度是 7 \times 2 = 14
- 马 2的满意度是 7 \times 2 = 14
本例中的总满意度为 32.
对于第二天的查询,如果马匹按顺序洗澡 4,2,1,3,每匹马的满意度如下:
- 马 4的满意度是 7
- 马 2的满意度是 7 \times 2 = 14
- 马 1的满意度是 3 \times 1 = 3
- 马 3的满意度是 3 \times 1 = 3
本例中的总满意度为 27.
对于第三天的查询,如果马匹按顺序洗澡 4,3,2,1,总满意度为 18.
对于第四天的查询,如果马匹按顺序洗澡 4,3,1,2,总满意度为 2000015.
示例输入 2
10 10 340019 2 598908 1 177330 2 575439 2 916653 2 451275 2 762769 2 36625 2 273231 2 367619 2 8 334230 2 8 835378 1 4 777076 2 6 61501 1 4 516395 1 4 35678 2 5 751493 1 3 815798 1 2 369777 2 5 941470 2
示例输出 2
9417616 10146681 10549955 9708906 8847525 8463663 7860112 8606740 8516097 9236070