← 返回题目列表

AtCoder · abc440_f

I. 利己主义

中文机器翻译题面 查看原题

分数: 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