P11859 [CCC 2025 Senior] 画画 / Pretty Pens

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

有 $n$ 支笔，$m$ 种颜色。第 $i$ 支笔的**颜色**为 $c_i$，**美丽度**为 $p_i$。 现在要用这些笔来画画。画会用到 $m$ 种颜色，所以要从每种颜色的笔中各选出一支，画的**美丽度**就是选出的笔的美丽度之和。 在下笔前，你可以选择**至多一支**笔，将这支笔的颜色改成 $[1,m]$ 中的任意一种。**画完后，这支笔的颜色将恢复为原本的颜色。** 有 $q$ 次操作： - $\texttt{1}$ $i$ $x$：令 $c_i\gets x$。 - $\texttt{2}$ $i$ $y$：令 $p_i\gets y$。 对于 $i=1,2,\ldots,q+1$，求出：在完成前 $(i-1)$ 次操作后，用这些笔画出画的美丽度最大值。 再次强调，**画完一幅画后，这支笔的颜色将恢复为原本的颜色。**

第一行，三个非负整数 $n,m,q$。 接下来 $n$ 行，每行两个正整数 $c_i,p_i$。 接下来 $q$ 行，每行三个正整数，描述一个操作。 数据保证，在任意时刻，每种颜色都至少有一支笔。

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

#### 样例解释 - 样例 $1$ 解释： 起初，有三种颜色的笔： - 颜色 $1$ 的笔的美丽度为 $3,6$。 - 颜色 $2$ 的笔的美丽度为 $7,9$。 - 颜色 $3$ 的笔的美丽度为 $4,9$。 如果不改变笔的颜色，画的最大美丽度为 $6+9+9=24$。 然而，将第 $4$ 支笔的颜色从 $2$ 改成 $1$ 可以获得 $7+9+9=25$ 的美丽度，这也是最优方案。 - 样例 $2$ 解释： 在第一次修改前和第二次修改前，选择第 $1,2$ 支笔是最优的。 在第二次修改后，选择第 $2,3$ 支笔是最优的。 #### 子任务 对于 $100\%$ 的数据，保证： - $1\le m\le n\le 2\times 10^5$； - $0\le q\le 2\times 10^5$； - $1\le c_i,x\le m$； - $1\le p_i,y\le 10^9$； - $1\le i\le n$； - 在任意时刻，每种颜色都至少有一支笔。 --- 子任务 $0$ 为样例。 | $\text{Subtask}$ | $n\le$ |$ m$ | $q\le $ | 特殊性质 | 得分 | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $2\times 10^5$ | $\le 2\times 10^5$ | $0$ | / | $5$ | | $2$ | $2\times 10^5$ | $=1$ | $\le 2\times 10^5$ | / | $2$ | | $3$ | $2\times 10^5$ | $=2$ | $\le 2\times 10^5$ | / | $2$ | | $4$ | $2\times 10^5$ | $\le 10$ | $\le 2\times 10^5$ | / | $2$ | | $5$ | $2\times 10^5$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\text{A}$ | $2$ | | $6$ | $2\times 10^5$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | / | $2$ | - 特殊性质 $\text{A}$：数据保证在任意时刻，$n$ 支笔的美丽度都是两两不同的。