P9638（2023 激励计划评分 5）

· · 题解

由于敏感值相对大小不会变化，所以图的形态最多只有 n 种。即按敏感值从小到大排序后断开一段前缀边。

先离线下来所有读入，每次 1 操作和 3 操作更新当前图的形态，对于询问操作直接在当前形态存储下来这次询问。最后利用并查集依次加边并处理询问即可。更新图的形态的时候可以使用二分法，总时间复杂度 O((n+q)\log n)。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define deb(x) cerr<<"Line: "<<__LINE__<<", val= "<<x<<"; \n"
typedef long long ll;
#define pii pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
const ll N=4e5+10;
inline ll read(){
    ll a=0,x=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  x=-x;
        c=getchar();
    }
    while(isdigit(c)){
        a=a*10+c-'0';
        c=getchar();
    }
    return a*x;
}
ll n,m,q,cnt;
ll fa[N],sz[N],pos[N],ans[N];
vector<pii> v[N];
struct Edge{
    ll x,y,k,bh;
    bool operator<(const Edge &a1) const{
        if(k==a1.k) return bh<a1.bh;
        return k<a1.k;
    }
}e[N];
ll get(ll x){
    if(x==fa[x])    return x;
    return fa[x]=get(fa[x]);
}
void merge(ll x,ll y){
    ll xx=get(x),yy=get(y);
    if(xx==yy)  return;
    if(sz[xx]>sz[yy])   swap(xx,yy);
    fa[xx]=yy,sz[yy]+=sz[xx];
}
signed main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;i++){
        e[i].x=read(),e[i].y=read(),e[i].k=read();
        e[i].bh=i;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++){
        fa[i]=i;sz[i]=1;
    }
    for(int i=1;i<=m;i++){
        pos[e[i].bh]=i;
    }
    ll nws=0,nwpos=0;
    while(q--){
        ll opt=read();
        if(opt==1){
            nws=read();
            nwpos=upper_bound(e+1,e+m+1,(Edge){0,0,nws,0})-e-1;
//          printf("%lld\n",nwpos);
        }   
        else if(opt==2){
            ll x=read();
            v[nwpos].push_back(mp(x,++cnt));
        }
        else{
            ll x=read(),nwf=read();
            e[pos[x]].k=nwf;
            nwpos=upper_bound(e+1,e+m+1,(Edge){0,0,nws,0})-e-1;
//          printf("%lld\n",nwpos);
        }
    }
    for(int i=m;i>=0;i--){
        for(int j=0;j<v[i].size();j++){
            ans[v[i][j].se]=sz[get(v[i][j].fi)];
        }
        if(i!=0)    merge(e[i].x,e[i].y);
    }
    for(int i=1;i<=cnt;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}