如题。大概就是第一篇题解没加后面的奇妙优化。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=2e5+10;
mt19937 rnd(time(0));
int n,m,k;
struct E{
    int tl,tr,u,v;
};vector<E>e;
struct Q{
    int id,t,p;
};
int cmp(Q p,Q q){return p.p<q.p;}
int cmp2(pair<int,int>p,pair<int,int>q){return p.second<q.second;}
map<pair<int,int>,int>mp;
const int B=400;
vector<pair<int,int>>q[N];//t,{p,id}
int ansl[N],ansr[N];
namespace DSU{
    vector<int>fa[N];
    vector<int>siz[N];
    int ID,CNT;
    int f[N],s[N],c[N];
    void init()
    {
        for ( int i = 1 ; i <= n ; i++ )
            fa[i].clear(),siz[i].clear();
        for ( int i = 1 ; i <= n ; i++ )fa[i].push_back(i),siz[i].push_back(1);
        assert(ID==0);
        ID=0;CNT=n;
    }
    int find_ys(int x)
    {
        if(x==fa[x].back())return x;
        return fa[x][fa[x].size()-1]=find_ys(fa[x].back());
    }
    int find(int x){return (x==fa[x].back()?x:find(fa[x].back()));}
    void merge_ys(int u,int v)
    {
        u=find_ys(u),v=find_ys(v);
        if(u==v)return;
        if(siz[u].back()>siz[v].back())swap(u,v);
        CNT--;
        fa[u][fa[u].size()-1]=v;
        siz[v][fa[v].size()-1]=siz[v].back()+siz[u].back();
    }
    void merge(int u,int v)
    {
        ID++;
        u=find(u),v=find(v);
        if(u==v)return;
        CNT--;c[ID]=1;
        fa[u].push_back(v);
        siz[v].push_back(siz[u].back()+siz[v].back());
        f[ID]=u,s[ID]=v;
    }
    void undo()
    {
        fa[f[ID]].pop_back();
        siz[s[ID]].pop_back();
        CNT+=c[ID];
        f[ID]=s[ID]=c[ID]=0;ID--;
    }
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin >> n >> m >> k;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int op,u,v;cin >> op >> u >> v;
        u++,v++;
        if(u>v)swap(u,v);
        if(op==0)mp[{u,v}]=i;
        else{
            e.push_back({mp[{u,v}],i-1,u,v});
            mp[{u,v}]=0;
        }
    }
    for ( auto x:mp )if(x.second)
        e.push_back({x.second,m,x.first.first,x.first.second});
    for ( int i = 1 ; i <= k ; i++ )
    {
        int p,t;cin >> t >> p;
        t++,p++;
        q[t].push_back({p,i});
    }
    DSU::CNT=n;
    for ( int i = 1 ; i <= (m+B-1)/B ; i++ )
    {
        int l=i*B-B+1,r=i*B;r=min(r,m);
        vector<pair<int,int>>v1;
        vector<E>v2;
        v1.clear(),v2.clear();
        for ( auto x:e )
        {
            if(x.tl<=l&&r<=x.tr)v1.push_back({x.u,x.v});
            else if(!((x.tr<l||r<x.tl)))v2.push_back(x);
        }
        sort(v1.begin(),v1.end(),cmp2);
        vector<Q>vq;vq.clear();
        for ( int j = l ; j <= r ; j++ )
            for ( auto x:q[j] )vq.push_back({x.second,j,x.first});
        sort(vq.begin(),vq.end(),cmp);
        int tp=0;
        DSU::init();
        for ( auto x:vq )
        {
            int id=x.id,p=x.p,t=x.t;
            while(tp<v1.size()&&v1[tp].second<=p)
            {
                DSU::merge_ys(v1[tp].first,v1[tp].second);
                tp++;
            }
            for ( auto y:v2 )
            {
                int tl=y.tl,tr=y.tr,u=y.u,v=y.v;
                if(v<=p&&tl<=t&&t<=tr)
                    DSU::merge(u,v);
            }
            ansl[id]=p-(n-DSU::CNT);
            for ( auto y:v2 )
            {
                int tl=y.tl,tr=y.tr,u=y.u,v=y.v;
                if(v<=p&&tl<=t&&t<=tr)DSU::undo();
            }
        }
        DSU::init();
        sort(v1.begin(),v1.end());
        tp=(signed)v1.size();
        reverse(vq.begin(),vq.end());
        for ( auto x:vq )
        {
            int id=x.id,p=x.p,t=x.t;
            while(tp>0&&p<v1[tp-1].first)
            {
                tp--;
                DSU::merge_ys(v1[tp].first,v1[tp].second);
            }
            for ( auto y:v2 )
            {
                int tl=y.tl,tr=y.tr,u=y.u,v=y.v;
                if(p<u&&tl<=t&&t<=tr)
                    DSU::merge(u,v);
            }
            ansr[id]=DSU::CNT-p;
            for ( auto y:v2 )
            {
                int tl=y.tl,tr=y.tr,u=y.u,v=y.v;
                if(p<u&&tl<=t&&t<=tr)DSU::undo();
            }
        }
    }
    for ( int i = 1 ; i <= k ; i++ )cout << ansl[i]+ansr[i] << "\n";
	return 0;
}

提交记录：https://www.luogu.com.cn/record/227551974