CF1789C题解

qvzeyang · 2023-09-16 19:42:00 · 个人记录

这是一道对2023年山东省队有重大意义的题目。

对每个颜色分别考虑，分开算贡献。 随便做做就行了。

打暴力省一，进特殊类别省队，拿压线银牌，度过相对成功的oi生涯！

upd：

    大结局，1789以山东清华强基最低分进入了致理信计，再次延续卡线神话！
    卡线又如何？多考一分都是浪费，这样的人生才可谓精彩吧！

代码如下：

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair
#define _(x,y) (x=(x+y)%mod)
#define ll long long
    #define int long long
using namespace std;
ll read(){char c=getchar();ll d=0,k=1;
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')k=-1,c=getchar();
while(c>='0' and c<='9')d=(d<<1)+(d<<3)+(c^48),c=getchar();return d*k;}

map<int,int>xiang_dui_cheng_gong_de_oi_sheng_ya;

int bao_li_sheng_yi[1000000],ya_xian_yin_pai[1000000],_1789_is_C,m,shan_dong_da_C_1789,_1789C;

vector<pr>te_shu_lei_bie_sheng_dui[1000000]; 

void insert(int x,int p){
    if(ya_xian_yin_pai[x]!=1)return;

    xiang_dui_cheng_gong_de_oi_sheng_ya[x]=p;
}

void del(int x,int p){
    if(ya_xian_yin_pai[x])return;

    te_shu_lei_bie_sheng_dui[x].push_back(mp(xiang_dui_cheng_gong_de_oi_sheng_ya[x],p-1));

    xiang_dui_cheng_gong_de_oi_sheng_ya[x]=-1;
}

signed main(){

    _1789C=read();

    while(_1789C--){

        shan_dong_da_C_1789=0;

        _1789_is_C=read(),m=read();

        for(int i=1;i<=_1789_is_C+m;i++){
            te_shu_lei_bie_sheng_dui[i].clear();

            ya_xian_yin_pai[i]=0;

            xiang_dui_cheng_gong_de_oi_sheng_ya[i]=-1;
        }
        for(int i=1;i<=_1789_is_C;i++){
            bao_li_sheng_yi[i]=read();

            ya_xian_yin_pai[bao_li_sheng_yi[i]]++;

            insert(bao_li_sheng_yi[i],0);
        }
        for(int i=1;i<=m;i++){
            int x=read(),v=read();

            ya_xian_yin_pai[bao_li_sheng_yi[x]]--;

            del(bao_li_sheng_yi[x],i);

            bao_li_sheng_yi[x]=v;

            ya_xian_yin_pai[bao_li_sheng_yi[x]]++;

            insert(bao_li_sheng_yi[x],i);
        }   
        for(int i=1;i<=_1789_is_C+m;i++)
            if(xiang_dui_cheng_gong_de_oi_sheng_ya[i]!=-1)
                te_shu_lei_bie_sheng_dui[i].push_back(mp(xiang_dui_cheng_gong_de_oi_sheng_ya[i],m));
        for(int i=1;i<=_1789_is_C+m;i++){
            int u=-1,sum=0;
            for(int j=0;j<te_shu_lei_bie_sheng_dui[i].size();j++){
                int l=te_shu_lei_bie_sheng_dui[i][j].first,r=te_shu_lei_bie_sheng_dui[i][j].second;

                shan_dong_da_C_1789+=(l-1-u)*sum;

                shan_dong_da_C_1789+=(r-l+1)*(l+r)/2;

                sum+=r-l+1;

                u=r;
            }
            shan_dong_da_C_1789+=(m-u)*sum;
        }

        cout<<shan_dong_da_C_1789<<endl;

    }

    return 0;
}