APIO场外选手没事休闲做题。(看了yyb的题解才把这题做出来)
对操作进行分块,把每\(\text{SZ}\)个操作分成1组,里面大概有2类:没被修改过的和被修改过的。
接着对块内询问进行离线。
对于没有修改过的:我们可以直接排序然后把他们加入并查集。
对于修改过的,我们看他的时间是否大于当前操作的时间,如果大于则加入原来的权值,如果小于则用修改后的权值。
最后答案其实就是查一下连通块的大小。
再注意一点,因为这里的并查集是支持撤回的,所以并不能路径压缩。
// luogu-judger-enable-o2
#include <bits/stdc++.h>
const int maxm = 1e5 + 10;
inline void _swap(int& a,int& b) { a ^= b ^= a ^= b; }
template<class T> inline void read(T& res) {
res = 0; char ch = getchar(); bool neg = 0;
while(!isdigit(ch))
neg |= ch == '-', ch = getchar();
while(isdigit(ch))
res = (res << 1) + (res << 3) + (ch & 15), ch = getchar();
if(neg)
res = -res;
}
int n, m, i, j, k, tote, totq, top, lastop, SZ;
int fa[maxm], sz[maxm], id[maxm], ans[maxm], r[maxm];
std::pair<int,int> sta[maxm];
int find(int u) { return u == fa[u] ? u : find(fa[u]); }
inline void Union(int u,int v) {
int ru = find(u), rv = find(v);
if(ru == rv)
return;
if(sz[ru] < sz[rv])
_swap(ru,rv);
fa[rv] = ru; sz[ru] += sz[rv];
sta[++top] = std::make_pair(ru,rv);
}
bool vis[maxm];
struct edge {
int u, v, w, id;
edge() { u = v = w = id = 0; }
edge(int _u,int _v,int _w,int _id) {
u = _u; v = _v; w = _w; id = _id;
}
inline friend bool operator < (edge a,edge b) {
if(a.w != b.w)
return a.w > b.w;
else
return a.id < b.id;
}
} e[maxm], e1[maxm], e2[maxm];
struct node {
int id, t, b, r;
node() { id = t = b = r = 0; }
node(int _id,int _t,int _b,int _r) {
id = _id; t = _t; b = _b; r = _r;
}
inline friend bool operator < (node a,node b) {
return a.b > b.b;
}
} Q[maxm], x[maxm], y[maxm];
inline void solve() {
memset(vis,0,sizeof(vis)); top = lastop = 0;
for(int i = 1;i <= n;i++)
fa[i] = i, sz[i] = 1;
int tot1 = 0, tot2 = 0;
for(int i = 1;i <= totq;i++) {
if(Q[i].t == 1)
vis[ Q[i].b ] = 1, x[++tot1] = Q[i];
else
y[++tot2] = Q[i];
}
std::sort(y + 1,y + tot2 + 1);
for(int i = 1;i <= m;i++)
id[ e[i].id ] = i;
int j = 1;
for(int i = 1;i <= tot2;i++) {
while(j <= m && e[j].w >= y[i].b) {
if(!vis[ e[j].id ])
Union(e[j].u,e[j].v);
j++;
}
lastop = top;
for(int j = 1;j <= tot1;j++)
r[ x[j].b ] = e[ id[ x[j].b ] ].w;
for(int j = 1;j <= tot1;j++)
if(x[j].id < y[i].id)
r[ x[j].b ] = x[j].r;
for(int j = 1;j <= tot1;j++)
if(r[ x[j].b ] >= y[i].b)
Union(e[ id[ x[j].b ] ].u,e[ id[ x[j].b ] ].v);
ans[ y[i].id ] = sz[ find(y[i].r) ];
while(top > lastop) {
int u = sta[top].first, v = sta[top].second;
top--;
fa[v] = v;
sz[u] -= sz[v];
}
}
for(int i = 1;i <= tot1;i++)
e[ id[ x[i].b ] ].w = x[i].r;
tot1 = tot2 = 0;
for(int i = 1;i <= m;i++) {
if(vis[ e[i].id ])
e1[++tot1] = e[i];
else
e[++tot2] = e[i];
}
std::sort(&e1[1],&e1[tot1 + 1]);
std::merge(&e[1],&e[tot2 + 1],&e1[1],&e1[tot1 + 1],&e2[1]);
for(int i = 1;i <= m;i++)
e[i] = e2[i];
}
int main() {
SZ = 500;
read(n); read(m);
for(int i = 1, u, v, w;i <= m;i++)
read(u), read(v), read(w), e[i] = edge(u,v,w,i);
std::sort(&e[1],&e[m + 1]);
int q; read(q);
for(int i = 1, op, x, y;i <= q;i++) {
read(op); read(x); read(y);
if(op == 2)
_swap(x,y);
Q[++totq] = node(i,op,x,y);
if(totq == SZ)
solve(), totq = 0;
}
if(totq)
solve();
for(int i = 1;i <= q;i++)
if(ans[i])
printf("%d\n",ans[i]);
return 0;
}