[CCC 2025 Senior] 画画 / Pretty Pens

[CCC 2025 Senior] 画画 / Pretty Pens

Problem

题目描述

小蒟参加了美术社，正在学习蜡笔画。他购买了 \(n\) 支笔，\(m\) 种颜色。第 \(i\) 支笔的颜色为 \(c_i\)，美丽度为 \(p_i\)。

现在他准备用这些画笔来创作一幅作品，当然根据美学，一幅画作不易过于复杂，所以他决定用 \(m\) 种颜色的蜡笔各画一笔，画作的美丽度就是用于创作的笔的美丽度之和。

社团的老师给了小蒟一些艺术表达空间：在创作这幅美观的画作之前，可以将最多一支笔更改为其他颜色。在画作完成后，笔将恢复其原始颜色。请你创作出美丽度最高的画作。

为了挑战小蒟的创意极限，社团老师还有\(q\)幅更多的画作让他创作。在每幅画作之前，画笔集合将有两种可能的更改：

• $1 \ i\ c \(表示第\)i\(支笔的颜色更改为\)c$。
• \(2\ i\ p\) 表示第i支笔的美丽度更改为\(p\)。

所有的更改都是按照顺序执行的，也就是第一个更改修改初始设置，第二个更改修改应用第一个更改后的结果，依此类推。

和小蒟蒻创作的第一幅画一样，他仍然可以将一直画笔的颜色修改。再次强调，画完一幅画后，这支笔的颜色将恢复为原本的颜色。也就是更改颜色只会影响下一幅画作。

Solution

按题意模拟即可

使用multiset维护每种颜色的笔的美丽值col，递增排列

此时定义ans为堆顶之和

因为有替换操作，额外维护选择的画笔chose和次大值rk2

检查替换是否可以使ans更优

将两种操作转换成画笔的删除和增加

动态维护这几个信息即可

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, q, c[N], p[N];
multiset <int, greater <int>> pen[N], rk2;
multiset <int> chose;
long long ans = 0;
int get_sec(int id) {
	int cnt = 1;
	for (auto v : pen[id]) {
		if (cnt == 2) return v;
		cnt++;
	}
}
void add(int id, int val) {
	if (pen[id].size()) ans -= *pen[id].begin();
	if (pen[id].size()) chose.erase(chose.find(*pen[id].begin()));
	if (pen[id].size() > 1) rk2.erase(rk2.find(get_sec(id)));
	
	pen[id].emplace(val);
	
	ans += *pen[id].begin();
	chose.emplace(*pen[id].begin());
	if (pen[id].size() > 1) rk2.emplace(get_sec(id));
}
void del(int id, int val) {
	if (pen[id].size()) ans -= *pen[id].begin();
	if (pen[id].size()) chose.erase(chose.find(*pen[id].begin()));
	if (pen[id].size() > 1) rk2.erase(rk2.find(get_sec(id)));
	
	pen[id].erase(pen[id].find(val));
	
	if (pen[id].size()) ans += *pen[id].begin();
	if (pen[id].size()) chose.emplace(*pen[id].begin());
	if (pen[id].size() > 1) rk2.emplace(get_sec(id));
}
signed main() {
	cin.tie(nullptr) -> ios::sync_with_stdio(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> p[i];
		add(c[i], p[i]);
	}
	
	if (chose.size() && rk2.size()) {
		if (*chose.begin() < *rk2.begin()) 
		cout << ans - *chose.begin() + *rk2.begin() << '\n';
		else
		cout << ans << '\n';
	} else {
		cout << ans << '\n';
	}
	while (q--) {
		int opt, id, x;
		cin >> opt >> id >> x;
		if (opt == 1) {
			del(c[id], p[id]);
			c[id] = x;
			add(c[id], p[id]);
		} else {
			del(c[id], p[id]);
			p[id] = x;
			add(c[id], p[id]);
		}
		
		if (chose.size() && rk2.size()) {
			if (*chose.begin() < *rk2.begin()) 
			cout << ans - *chose.begin() + *rk2.begin() << '\n';
			else
			cout << ans << '\n';
		} else {
			cout << ans << '\n';
		}
	}
	return 0;
}