#P11859. [CCC 2025 Senior] 画画 / Pretty Pens

[CCC 2025 Senior] 画画 / Pretty Pens

题目背景

译自 CCC 2025 Senior T3。本题满分为 1515

题目描述

nn 支笔,mm 种颜色。第 ii 支笔的颜色cic_i美丽度pip_i

现在要用这些笔来画画。画会用到 mm 种颜色,所以要从每种颜色的笔中各选出一支,画的美丽度就是选出的笔的美丽度之和。

在下笔前,你可以选择至多一支笔,将这支笔的颜色改成 [1,m][1,m] 中的任意一种。画完后,这支笔的颜色将恢复为原本的颜色。

qq 次操作:

  • 1\texttt{1} ii xx:令 cixc_i\gets x
  • 2\texttt{2} ii yy:令 piyp_i\gets y

对于 i=1,2,,q+1i=1,2,\ldots,q+1,求出:在完成前 (i1)(i-1) 次操作后,用这些笔画出画的美丽度最大值。

再次强调,画完一幅画后,这支笔的颜色将恢复为原本的颜色。

输入格式

第一行,三个非负整数 n,m,qn,m,q

接下来 nn 行,每行两个正整数 ci,pic_i,p_i

接下来 qq 行,每行三个正整数,描述一个操作。

数据保证,在任意时刻,每种颜色都至少有一支笔。

输出格式

输出 (q+1)(q+1) 行,第 ii 行的正整数表示完成前 (i1)(i-1) 次操作后,用这些笔画出画的美丽度最大值。

6 3 0
1 6
2 9
3 4
2 7
3 9
1 3
25
3 2 2
1 20
2 30
1 10
1 3 2
2 3 25
50
50
55

提示

样例解释

  • 样例 11 解释:

起初,有三种颜色的笔:

  • 颜色 11 的笔的美丽度为 3,63,6
  • 颜色 22 的笔的美丽度为 7,97,9
  • 颜色 33 的笔的美丽度为 4,94,9

如果不改变笔的颜色,画的最大美丽度为 6+9+9=246+9+9=24

然而,将第 44 支笔的颜色从 22 改成 11 可以获得 7+9+9=257+9+9=25 的美丽度,这也是最优方案。

  • 样例 22 解释:

在第一次修改前和第二次修改前,选择第 1,21,2 支笔是最优的。

在第二次修改后,选择第 2,32,3 支笔是最优的。

子任务

对于 100%100\% 的数据,保证:

  • 1mn2×1051\le m\le n\le 2\times 10^5
  • 0q2×1050\le q\le 2\times 10^5
  • 1ci,xm1\le c_i,x\le m
  • 1pi,y1091\le p_i,y\le 10^9
  • 1in1\le i\le n
  • 在任意时刻,每种颜色都至少有一支笔。

子任务 00 为样例。

Subtask\text{Subtask} nn\le m m qq\le 特殊性质 得分
11 2×1052\times 10^5 2×105\le 2\times 10^5 00 / 55
22 =1=1 2×105\le 2\times 10^5 22
33 =2=2
44 10\le 10
55 2×105\le 2\times 10^5 A\text{A}
66 /
  • 特殊性质 A\text{A}:数据保证在任意时刻,nn 支笔的美丽度都是两两不同的。