哈希表怎么这么慢。

枚举一个公司选的等级，另一个公司选的等级肯定是单调变化的，考虑双指针一下，问题边为一侧加边一侧删边问满足题意的住户对数量。

考虑直接用连通块染色来刻画这件事，记录点 $u$ 的信息为 $(a_u,b_u)$ 分别为在两类边构成的图中所属连通块的颜色。

加边启发式合并，删边启发式分裂，问题变成 $O(n \log n)$ 次修改一个点的信息与查询 $a_u=a_v$ 或者 $b_u=b_v$ 的点对 $(u,v)$ 数目，虽然不太好直接维护，但是修改过程中的合法点对增量是容易维护的，用哈希表记一下 $cnt_{i,j}$ 表示 $a_u=i,b_u=j$ 的 $u$ 数目即可。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fst first
#define sec second
#define pb push_back
const int maxn = 2e5+114;
int col[maxn];//颜色
int id[maxn];//连通块编号
vector< pair<int,vector<int> > > opt[maxn];//(C,S) 删除边 i 后的操作为将 S 中的点连通块划分为 C
unordered_map<int,int> cnt[maxn];//颜色为 i 的点中有多少个连通块编号为 j
int sum[maxn];//颜色为 i 的点的数量 
int fsum[maxn];//连通块 i 中点的数量
vector<int> S[maxn];//连通块 i 中的点
pair<int,pair<int,int> > e1[maxn],e2[maxn];
int n,m1,m2,k;
int Now;//目前联通的点对数
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m1>>m2>>k;
    for(int i=1;i<=m1;i++){
        cin>>e1[i].sec.fst>>e1[i].sec.sec>>e1[i].fst;
    }
    for(int i=1;i<=m2;i++){
        cin>>e2[i].sec.fst>>e2[i].sec.sec>>e2[i].fst;
    }
    sort(e1+1,e1+m1+1);
    sort(e2+1,e2+m2+1);
    for(int i=1;i<=n;i++) S[i].pb(i),col[i]=i;
    int ans=(k==0?0:1e18);
    for(int i=1;i<=m1;i++){
        int u=col[e1[i].sec.fst],v=col[e1[i].sec.sec];
        if(u!=v){
            if(S[u].size()<S[v].size()) swap(u,v);
            Now+=S[u].size()*S[v].size();
            opt[i].pb({v,S[v]});
            for(int x:S[v]){
                col[x]=u;
                S[u].pb(x);
            }
            S[v].clear();   
        }
        if(Now>=k) ans=min(ans,e1[i].fst);
    }
    for(int i=1;i<=n;i++) S[i].clear();
    for(int i=1;i<=n;i++){
        cnt[i][col[i]]++;
        sum[i]++;
        fsum[col[i]]++;
        id[i]=col[i];
    }
    for(int i=1;i<=n;i++) S[i].pb(i),col[i]=i;
    int tp=0;
    for(int i=m1;i>=0;i--){
        while(tp+1<=m2&&Now<k){
            tp++;
            int u=col[e2[tp].sec.fst],v=col[e2[tp].sec.sec];
            if(u==v) continue;
            if(S[u].size()<S[v].size()) swap(u,v);
            //v 合并到 u 上
            //先计算变化再增加
            for(int x:S[v]){
                //颜色为 u 并且所属连通块不是 id[x]
                Now+=sum[u]-cnt[u][id[x]];
            }
            for(int x:S[v]){
                cnt[col[x]][id[x]]--;
                sum[col[x]]--;
                col[x]=u;
                cnt[col[x]][id[x]]++;
                sum[col[x]]++;
                S[u].pb(x);
            }
            S[v].clear();
        }
        if(Now>=k) ans=min(ans,e1[i].fst+e2[tp].fst);
        if(i==0) break;
        //撤销边 i 还原一些连通块
        for(pair<int,vector<int> > now:opt[i]){
            //先减少再计算变化
            int lstid=-1;
            for(int x:now.sec){
                lstid=id[x];
                cnt[col[x]][id[x]]--;
                fsum[id[x]]--;
                id[x]=now.fst;
                fsum[id[x]]++;
                cnt[col[x]][id[x]]++;
            }
            for(int x:now.sec){
                //连通块为 lstid 颜色不为 col[x]
                Now-=fsum[lstid]-cnt[col[x]][lstid];
            }
        }
    }
    cout<<(ans==1e18?-1:ans)<<"\n";
    return 0;
}