三天终于把(APIO)做完了
这题还是比较厉害的，如果不知道这是个分块应该就自闭了
考虑一个非常妙的操作，按照操作分块
我们设一个闸值(S)，把(S)个边权修改操作分成一块，把所有的边分成两类，一类是在这个块内被修改过的边，一类是没有被修改过的边
我们把没有被修改过的边按照边权离线，同时把这个块内所有的询问离线，用并查集来维护这张图，只需要保证进行一次询问之前图中只有边权大于等于它的边
进行询问的时候当然还得考虑这个块内被修改过的边的贡献，对于这个块内被修改过但是修改的时间大于当前询问的，我们直接按照原来的权值把它加入并查集；对于修改时间小于询问时间的边，我们把其最后一次被修改的权值加入并查集
这个时候只需要查询一下询问所在联通块大小就好了
我们发现这里的这些操作还需要支持撤回，所以并查集就不能路径压缩了
但是卡卡常就过去了
代码
#include<bits/stdc++.h>
#define re register
#pragma GCC optimize(3)
#pragma GCC optimize("-fcse-skip-blocks")
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
char BB[1<<18],*S=BB,*T=BB;
const int maxn=1e5+5;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct Edge{int u,v,rk,t,o,w;}e[maxn],r[maxn];
struct Ask{int o,x,y,rk;}q[maxn],g[maxn];
inline int cmp(const Edge &A,const Edge &B) {return A.o==B.o?A.w>B.w:A.o<B.o;}
inline int ctp(const Edge &A,const Edge &B) {return A.t<B.t;}
inline int cxp(const Ask &A,const Ask &B) {return A.y>B.y;}
inline int cop(const Edge &A,const Edge &B) {return A.rk<B.rk;}
int n,m,cnt,s,Q,now;
int fa[maxn],sz[maxn],st1[maxn],st2[maxn],f[maxn],top,Ans[maxn],st[maxn],pt,U[maxn],V[maxn];
inline int find(int x) {while(x!=fa[x]) x=fa[x];return x;}
inline void back(int x) {sz[st1[x]]-=sz[st2[x]];fa[st2[x]]=st2[x];}
inline void merge(int x,int y) {
int xx=find(x),yy=find(y);
if(xx==yy) return;
if(sz[xx]<sz[yy]) fa[xx]=yy,sz[yy]+=sz[xx],st1[++top]=yy,st2[top]=xx;
else fa[yy]=xx,sz[xx]+=sz[yy],st1[++top]=xx,st2[top]=yy;
}
inline void calc(int t) {
for(re int i=1;i<=now;i++) {
if(r[i].t>g[t].rk) break;
if(!f[r[i].rk]) st[++pt]=r[i].rk,U[pt]=r[i].u,V[pt]=r[i].v;
f[r[i].rk]=q[r[i].t].y;
}
for(re int i=now;i;--i) {
if(r[i].t<g[t].rk) break;
if(r[i].t>g[t].rk&&!f[r[i].rk]&&r[i].w>=g[t].y)
merge(r[i].u,r[i].v);
}
while(pt) {
if(f[st[pt]]>=g[t].y) merge(U[pt],V[pt]);
f[st[pt]]=0;--pt;
}
Ans[g[t].rk]=sz[find(g[t].x)];
while(top) back(top--);
}
inline void solve(int L,int R) {
if(L>R) return;
int H=0,tot=1;now=0;
for(re int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
for(re int i=L;i<=R;i++)
if(q[i].o==1) e[q[i].x].t=i,e[q[i].x].o=1,r[++now]=e[q[i].x];
else g[++H]=q[i];
std::sort(r+1,r+now+1,ctp);
std::sort(g+1,g+H+1,cxp);std::sort(e+1,e+m+1,cmp);
for(re int i=1;i<=m;i++) {
if(e[i].o) break;
while(tot<=H&&e[i].w<g[tot].y) calc(tot),tot++;
int xx=find(e[i].u),yy=find(e[i].v);
if(xx!=yy) {
if(sz[xx]<=sz[yy]) sz[yy]+=sz[xx],fa[xx]=yy;
else sz[xx]+=sz[yy],fa[yy]=xx;
}
}
while(tot<=H) calc(tot),tot++;
std::sort(e+1,e+m+1,cop);
for(re int i=L;i<=R;i++) if(q[i].o==1) e[q[i].x].o=0,e[q[i].x].w=q[i].y;
}
int main() {
n=read(),m=read();
for(re int i=1;i<=m;i++)
e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].rk=i;
Q=read();s=3.4*std::sqrt(m);
int l=1;
for(re int i=1;i<=Q;i++) {
q[i].o=read(),q[i].x=read(),q[i].y=read();q[i].rk=i;
if(q[i].o==1) ++cnt;
if(cnt>=s) solve(l,i),cnt=0,l=i+1;
}
solve(l,Q);
for(re int i=1;i<=Q;i++) if(q[i].o==2) printf("%d
",Ans[i]);
return 0;
}