#include<bits/stdc++.h>
using namespace std;
#define debug(...) 42
const int maxn = 1e5 + 1;
const int block = 1000;
int sz[maxn], par[maxn], n, m, q;
stack<pair<int&,int>> stk;
void reset(){
iota(par + 1, par + n + 1, 1);
fill(sz + 1, sz + n + 1, 1);
}
int find(int a){
return (a == par[a]) ? a : par[a] = find(par[a]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
stk.push({sz[a], sz[a]});
stk.push({par[b], par[b]});
sz[a] += sz[b];
par[b] = a;
}
void rollback(int x){
while(stk.size() > x){
auto [a, b] = stk.top();
a = b;
stk.pop();
}
}
int u[maxn], v[maxn], w[maxn], t[maxn], x[maxn], y[maxn];
bool changed[maxn];
vector<int> join[block];
int ans[maxn];
void solve(){
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];
cin >> q;
debug(n, m, q);
for (int i = 1; i <= q; i++) cin >> t[i] >> x[i] >> y[i];
for (int l = 1; l <= q; l += block){
int r = min(q + 1, l + block);
reset();
fill(changed + 1, changed + m + 1, false);
vector<int> ask, up, unchanged;
for (int i = l; i < r; i++){
if (t[i] == 1){
changed[x[i]] = true;
up.push_back(i);
}
else ask.push_back(i);
}
for (int i = 1; i <= m; i++) if (!changed[i]) unchanged.push_back(i);
for (int i = l; i < r; i++){
if (t[i] == 1){
w[x[i]] = y[i];
}
else{
join[i - l].clear();
for (auto j : up) {
if (w[x[j]] >= y[i]) join[i - l].push_back(x[j]);
}
}
}
sort(ask.begin(), ask.end(), [&] (int i, int j){
return y[i] > y[j];
});
sort(unchanged.begin(), unchanged.end(), [&] (int i, int j){
return w[i] > w[j];
});
int it = 0;
for (auto i : ask){
while(it < unchanged.size() && w[unchanged[it]] >= y[i]){
merge(u[unchanged[it]], v[unchanged[it]]);
it++;
}
int prev = stk.size();
for (auto j : join[i - l]) merge(u[j], v[j]);
ans[i] = sz[find(x[i])];
rollback(prev);
}
}
for (int i = 1; i <= q; i++) if (t[i] == 2) cout << ans[i] << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--){
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |