题解：P11859 [CCC 2025 Senior] 画画 / Pretty Pens

Acit · 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;
}