自动搬运

查看原文

来自洛谷，原作者为

	Acit ..

搬运于2025-08-24 23:10:52，当前版本为作者最后更新于2025-03-07 23:19:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

不难发现如果要更改颜色，应该用每种颜色的次大值的最大值替换最大值最小的那种颜色（用最大值替换后选择次大值与之是等价的）。

明白这一点后就很简单了，我们可以用 multiset 维护每种颜色的最大值，以及最大值和次大值集合，查询时简单判断即可（注释在代码里）。

Code

#include<bits/stdc++.h>
#define int long long
#define SET multiset<int>::iterator
using namespace std;
const int N=2e5+10;
int n,m,q,totmx;
//totmx是最大值之和
int c[N],p[N];
multiset<int> st[N];
multiset<int> secmx,mx;
void delsec(int x){
	//在次大值集合中删除某颜色集合的次大值
	if(st[x].size()>1){
		SET T=st[x].end();
		T--;T--;
		secmx.erase(secmx.lower_bound(*T));
	}
}
void delmx(int x){
	//在最大值集合中删除某颜色集合的最大值
	if(st[x].size()>=1){
		SET T=st[x].end();
		T--;
		totmx-=(*T);
		mx.erase(mx.lower_bound(*T));
	}
}
void addsec(int x){
	//在次大值集合中加入某颜色集合的次大值
	if(st[x].size()>1){
		SET T=st[x].end();
		T--;T--;
		secmx.insert(*T);
	}
}
void addmx(int x){
	//在最大值集合中加入某颜色集合的最大值
	if(st[x].size()>=1){
		SET T=st[x].end();
		T--;
		totmx+=(*T);
		mx.insert(*T);
	}
}
void out(){
	int ans=totmx;
	int ssmx=0;
	if(secmx.size()>=1){
		SET T=secmx.end();
		T--;
		ssmx=*T;
		//ssmx是次大值的最大值
	}
	ans=max(ans,ans-*mx.begin()+ssmx);//判断更改颜色是否更优
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)cin>>c[i]>>p[i],st[c[i]].insert(p[i]);
	for(int i=1;i<=m;i++){
		addsec(i);addmx(i);
		//初始化集合
	}
	out();
	for(int i=1;i<=q;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			delsec(c[x]);delsec(y);delmx(c[x]);delmx(y);
			st[c[x]].erase(st[c[x]].lower_bound(p[x]));
			st[y].insert(p[x]);
			addsec(c[x]);addsec(y);addmx(c[x]);addmx(y);
			c[x]=y;
			//注意在更改前删去更改集合的最大值和次大值，改完后加回来
		}
		else if(op==2){
			delsec(c[x]);delmx(c[x]);
			st[c[x]].erase(st[c[x]].lower_bound(p[x]));
			st[c[x]].insert(y);
			addsec(c[x]);addmx(c[x]);
			p[x]=y;
		}
		out();
	}
	return 0;
}