题解：P9638 「yyOI R1」youyou 的军训

Targanzqq · 2025-09-15 21:54:50 · 题解

给一个只需要 kruskal 跑最大生成树的做法。

我们对于每个查询，需要找到距离它最近且它可以走的边。那么我们只需要动态维护每条边的大小并且用一个 set 去找就可以。下面是具体维护方法：

• 每次进行 1 操作时就改一下当前的下限，然后执行队列里面的 3 操作，具体见下文。

• 进行 2 操作时就从 set 里面通过边权找边，然后把询问扔进这条边维护的 vector 里面。

• 进行 3 操作时就把它扔进一个队列里面，等到下一次 1 操作结束后再一起执行，执行方法也是从 set 里面通过原边权找边，然后用新边权替换就可以。

到了生成树部分，我们发现一条边包含的询问里面并不会有冲突，因为既然这个询问能放到这条边下，那就说明无论这条边被怎样修改，它都是最接近这个询问中点可以走的最小的边。因此我们按照 kruskal 从大到小加边维护并查集，每次到一条边的时候去找询问中点所在连通块的大小就可以。

总时间复杂度 O(m\log m)。

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
using namespace std;

int n,m,q,fa[400005],sz[400005],ans[400005],nw[400005];
struct edge{
    int u,v,w;
    friend bool operator<(edge a,edge b){
        return a.w>b.w;
    }
}e[400005];
multiset<pii> st;
vector<pii> ask[400005];

int find(int a){
    if(fa[a]==a)return a;
    return fa[a]=find(fa[a]);
}
void merge(int u,int v){
    if(sz[u]<sz[v])swap(u,v);
    fa[v]=u;sz[u]+=sz[v];sz[v]=0;
}
queue<pii> que;

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        st.insert(mp(e[i].w,i));nw[i]=e[i].w;
    }
    int now=0;
    for(int i=1;i<=q;i++){
        int op,x,y;cin>>op;
        if(op==1){
            cin>>x;now=x;
            while(!que.empty()){
                x=que.fr.fi,y=que.fr.se;que.pop();
                auto pos=st.lower_bound(mp(nw[x],x));
                st.erase(pos);st.insert(mp(y,x));nw[x]=y;
            }
        }
        if(op==2){
            cin>>x;auto pos=st.lower_bound(mp(now,0));
            if(pos==st.end()){ans[i]=1;continue;}
            int k=pos->se;ask[k].push_back(mp(x,i));
        }
        if(op==3){
            cin>>x>>y;que.push(mp(x,y));
            if(now>0)continue;
            while(!que.empty()){
                x=que.fr.fi,y=que.fr.se;que.pop();
                auto pos=st.lower_bound(mp(nw[x],x));
                st.erase(pos);st.insert(mp(y,x));nw[x]=y;
            }
        }
    }
    for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        int fau=find(u),fav=find(v);
        if(fau!=fav)merge(fau,fav);
        for(auto j:ask[i]){
            int fax=find(j.fi);ans[j.se]=sz[fax];
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[i])cout<<ans[i]<<"\n";
    }
}