本题是一道细节巨多的操作分块题。

踩坑记录

  • 一个块中有可能多次修改一条边（个人认为是本题最难部分）。

  • set的erase会直接删除所有不大于且不小于传入变量的键值，所以一定要好好写 operator 使其可以匹配唯一键值。

  • 变量多了一定要打注释，在这方面一定不要相信你的大脑。

  • 即使你很确定错误在哪，也要看看别的地方，不要像我瞪了半小时才知道错误在屏幕外。

AC 代码

自己都觉得又臭又长

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
const int maxn=100012;
int n,m,q,Sz,tp[maxn],ml[maxn],sz[maxn],tot,sta[maxn],fa[maxn],al[maxn],bl[maxn],wl[maxn],tl[maxn],pl[maxn];
struct edg
{
    int w,id;
    bool operator<(const edg y)const
    {
        return w!=y.w?w>y.w:id<y.id;
    }
};
set<edg>st;
list<edg>stk;
struct qry
{
    int tp,ml,w,id,ans;
}ql[maxn];
inline bool cmpq(const qry x,const qry y)
{
    return x.w>y.w;
}
inline bool cmpqb(const qry x,const qry y)
{
    return x.id<y.id;
}
int fdf(int x){while(x^fa[x])x=fa[x];return x;}
void mge(int a,int b)
{
    a=fdf(a);b=fdf(b);
    if(a^b)
    {
        if(sz[a]>sz[b])swap(a,b);
        // cout<<"mge"<<a<<' '<<b<<endl;
        sz[b]+=sz[a];fa[a]=b;sta[++tot]=a;
    }
}
void undo(int x)
{
    int dc;
    while(sta[tot]^x)
    {
        dc=sta[tot--];
        // cout<<"unmge"<<dc<<' '<<fa[dc]<<endl;
        sz[fa[dc]]-=sz[dc];
        fa[dc]=dc;
    }
}
bool b[maxn];
int main()
{
    // fio(05);
    n=in();m=in();
    fru(i,1,n)
    {
        sz[i]=1;
        fa[i]=i;
    }
    fru(i,1,m)
    {
        al[i]=in();bl[i]=in();wl[i]=in();
        st.emplace((edg){wl[i],i});
    }
    q=in();Sz=max((int)sqrt(n*__lg(n)),1);
    // cout<<"ssssssz"<<Sz<<endl;
    fru(i,1,q)
    {
        ql[i].tp=in();ql[i].ml=in();ql[i].w=in();ql[i].id=i;
    }
    int bk,stab;auto dc=st.begin();
    for(int i=1;i<=q;i+=Sz)
    {
        bk=min(q,i+Sz-1);
        fru(j,1,m)b[j]=false;
        fru(j,i,bk)
            if(ql[j].tp==1)
            {
                b[ql[j].ml]=true;stk.emplace_back((edg){wl[ql[j].ml],ql[j].ml});
            }
        sort(ql+i,ql+bk+1,cmpq);
        dc=st.begin();
        undo(0);
        // for(auto j:st)
        // {
        // 	cout<<j.id<<'S'<<al[j.id]<<'S'<<bl[j.id]<<'S'<<j.w<<endl;
        // }
        fru(j,i,bk)
            if(ql[j].tp==2)
            {
                for(;dc!=st.end();++dc)
                {
                    // cout<<(*dc).id<<' '<<(*dc).w<<endl;
                    if((*dc).w>=ql[j].w)
                    {
                        if(!b[(*dc).id])mge(al[(*dc).id],bl[(*dc).id]);
                        // cout<<"mengesort"<<endl;
                    }
                    else break;
                }
                stab=sta[tot];
                for(auto k:stk)
                {
                    tl[k.id]=0;pl[k.id]=wl[k.id];
                }
                fru(k,i,bk)
                if(ql[k].tp==1&&ql[k].id<ql[j].id)
                {
                        if(tl[ql[k].ml]<ql[k].id)
                        {
                            tl[ql[k].ml]=ql[k].id;
                            pl[ql[k].ml]=ql[k].w;
                        }
                }
                for(auto k:stk)
                {
                    if(pl[k.id]>=ql[j].w)mge(al[k.id],bl[k.id]);
                }
                ql[j].ans=sz[fdf(ql[j].ml)];
                // cout<<"sol"<<ql[j].id<<' '<<ql[j].ans<<endl;
                undo(stab);
            }
        for(auto j:stk)
        {
            st.erase(j);
            // cout<<"erase"<<j.id<<' '<<j.w<<endl;
        }
        stk.clear();
        sort(ql+i,ql+bk+1,cmpqb);
        fru(j,i,bk)
            if(ql[j].tp==1)
            {
                wl[ql[j].ml]=ql[j].w;
                // cout<<"insert"<<ql[j].w<<' '<<ql[j].ml<<endl;
            }
        fru(j,i,bk)
            if(ql[j].tp==1&&wl[ql[j].ml]==ql[j].w)
            {
                st.emplace((edg){ql[j].w,ql[j].ml});
                // cout<<"insert"<<ql[j].w<<' '<<ql[j].ml<<endl;
            }
    }
    sort(ql+1,ql+q+1,cmpqb);
    fru(i,1,q)
    {
        if(ql[i].tp==2)
        {
            printf("%d\n",ql[i].ans);
        }
    }
    return 0;
}