#include <bits/stdc++.h>
using namespace std;
#define size __size__
#define union __union__
const int can = 350;
int n,m,q;
struct __ {
int u,v,w,index;
bool operator < (const __ & other) {
return w < other.w;
}
} edge[100009];
bool changed[100009];
int uniq,firsttime[100009];
int root[100009],size[100009];
int getroot(int node) {
return (node == root[node] ? node : root[node] = getroot(root[node]));
}
void union(int u,int v) {
u = getroot(u),v = getroot(v);
if (u != v) root[u] = v,size[v] += size[u];
}
struct data {
int index,rootbefore,sizebefore,rootafter,sizeafter;
};
int getroot(int node,vector <data> & record) {
if (node == root[node]) return node;
int d = getroot(root[node],record);
record.push_back({node,root[node],size[node],d,size[node]});
root[node] = d;
return d;
}
void union(int u,int v,vector <data> & record) {
u = getroot(u,record);
v = getroot(v,record);
if (u == v) return;
record.push_back({u,root[u],size[u],v,size[u]});
root[u] = v;
record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
size[v] += size[u];
}
void rollback(vector <data> & record) {
reverse(record.begin(),record.end());
for (auto d : record) {
root[d.index] = d.rootbefore;
size[d.index] = d.sizebefore;
}
}
struct query {
int op,x,y,index;
} ask[100009];
__ bridges[100009];
int answer[100009];
int main() {
ios_base::sync_with_stdio(0);cin.tie(nullptr);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin >> n >> m;
for (int i = 1;i <= m;i++) {
cin >> edge[i].u >> edge[i].v >> edge[i].w;
edge[i].index = i;
}
cin >> q;
for (int ____ = 0;;____++) {
int l = max(1,____ * can),r = min(q,(____ + 1)*can - 1);
vector <query> contain;
for (int i = l;i <= r;i++) {
cin >> ask[i].op >> ask[i].x >> ask[i].y;
ask[i].index = i;
if (ask[i].op == 1) {
changed[ask[i].x] = 1;
bridges[i] = edge[ask[i].x];
}
else contain.push_back(ask[i]);
}
for (int i = 1;i <= n;i++) root[i] = i,size[i] = 1;
sort(contain.begin(),contain.end(),[] (query a,query b) {
return a.y > b.y;
});
sort(edge + 1,edge + 1 + m);
int pt = m + 1;
for (auto d : contain) {
int minimum = d.y,island = d.x;
while (pt > 1 && edge[pt - 1].w >= minimum) {
pt--;
if (!changed[edge[pt].index]) union(edge[pt].u,edge[pt].v);
}
vector <data> record;
uniq++;
for (int i = d.index - 1;i >= l;i--) if (ask[i].op == 1) {
__ bridge = bridges[i];
int w = ask[i].y;
if (firsttime[bridge.index] == uniq) continue;
firsttime[bridge.index] = uniq;
if (w >= minimum) union(bridge.u,bridge.v,record);
}
for (int i = d.index + 1;i <= r;i++) if (ask[i].op == 1) {
__ bridge = bridges[i];
if (firsttime[bridge.index] == uniq) continue;
if (bridge.w >= minimum) union(bridge.u,bridge.v,record);
}
answer[d.index] = size[getroot(island,record)];
rollback(record);
}
sort(edge + 1,edge + 1 + m,[] (__ a,__ b) {
return a.index < b.index;
});
for (int i = l;i <= r;i++) if (ask[i].op == 1) {
changed[ask[i].x] = 0;
edge[ask[i].x].w = ask[i].y;
}
if (r == q) break;
}
for (int i = 1;i <= q;i++) if (ask[i].op == 2) cout << answer[i] << '\n';
}
/*
Nho doi vai em gay
co gai ay ngoi duoi goc pho nen tho ...
*/
Compilation message (stderr)
bridges.cpp:37:34: error: template argument 1 is invalid
37 | int getroot(int node,vector <data> & record) {
| ^
bridges.cpp:37:34: error: template argument 2 is invalid
bridges.cpp:37:34: error: template argument 1 is invalid
bridges.cpp:37:34: error: template argument 2 is invalid
bridges.cpp:37:34: error: template argument 1 is invalid
bridges.cpp:37:34: error: template argument 2 is invalid
bridges.cpp:37:22: error: invalid template-id
37 | int getroot(int node,vector <data> & record) {
| ^~~~~~
bridges.cpp:37:30: error: reference to 'data' is ambiguous
37 | int getroot(int node,vector <data> & record) {
| ^~~~
In file included from /usr/include/c++/13/string:53,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
from bridges.cpp:1:
/usr/include/c++/13/bits/range_access.h:346:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
346 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:336:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
336 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:325:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
325 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/13/bits/range_access.h:314:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
314 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
bridges.cpp:33:8: note: 'struct data'
33 | struct data {
| ^~~~
bridges.cpp:37:22: error: missing template argument list after 'std::vector'; template placeholder not permitted in parameter
37 | int getroot(int node,vector <data> & record) {
| ^~~~~~
| <>
In file included from /usr/include/c++/13/vector:66,
from /usr/include/c++/13/functional:64,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:428:11: note: 'template<class _Tp, class _Alloc> class std::vector' declared here
428 | class vector : protected _Vector_base<_Tp, _Alloc>
| ^~~~~~
bridges.cpp: In function 'int getroot(...)':
bridges.cpp:39:36: error: 'record' was not declared in this scope
39 | int d = getroot(root[node],record);
| ^~~~~~
bridges.cpp: At global scope:
bridges.cpp:44:36: error: template argument 1 is invalid
44 | void union(int u,int v,vector <data> & record) {
| ^
bridges.cpp:44:36: error: template argument 2 is invalid
bridges.cpp:44:36: error: template argument 1 is invalid
bridges.cpp:44:36: error: template argument 2 is invalid
bridges.cpp:44:36: error: template argument 1 is invalid
bridges.cpp:44:36: error: template argument 2 is invalid
bridges.cpp:44:24: error: invalid template-id
44 | void union(int u,int v,vector <data> & record) {
| ^~~~~~
bridges.cpp:44:32: error: reference to 'data' is ambiguous
44 | void union(int u,int v,vector <data> & record) {
| ^~~~
/usr/include/c++/13/bits/range_access.h:346:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
346 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:336:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
336 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:325:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
325 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/13/bits/range_access.h:314:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
314 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
bridges.cpp:33:8: note: 'struct data'
33 | struct data {
| ^~~~
bridges.cpp:44:24: error: missing template argument list after 'std::vector'; template placeholder not permitted in parameter
44 | void union(int u,int v,vector <data> & record) {
| ^~~~~~
| <>
/usr/include/c++/13/bits/stl_vector.h:428:11: note: 'template<class _Tp, class _Alloc> class std::vector' declared here
428 | class vector : protected _Vector_base<_Tp, _Alloc>
| ^~~~~~
bridges.cpp: In function 'void __union__(...)':
bridges.cpp:45:23: error: 'record' was not declared in this scope
45 | u = getroot(u,record);
| ^~~~~~
bridges.cpp: At global scope:
bridges.cpp:57:27: error: template argument 1 is invalid
57 | void rollback(vector <data> & record) {
| ^
bridges.cpp:57:27: error: template argument 2 is invalid
bridges.cpp:57:27: error: template argument 1 is invalid
bridges.cpp:57:27: error: template argument 2 is invalid
bridges.cpp:57:27: error: template argument 1 is invalid
bridges.cpp:57:27: error: template argument 2 is invalid
bridges.cpp:57:15: error: invalid template-id
57 | void rollback(vector <data> & record) {
| ^~~~~~
bridges.cpp:57:6: error: variable or field 'rollback' declared void
57 | void rollback(vector <data> & record) {
| ^~~~~~~~
bridges.cpp:57:29: error: missing template arguments before '&' token
57 | void rollback(vector <data> & record) {
| ^
bridges.cpp:57:31: error: 'record' was not declared in this scope
57 | void rollback(vector <data> & record) {
| ^~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:113:37: error: template argument 1 is invalid
113 | vector <data> record;
| ^
bridges.cpp:113:37: error: template argument 2 is invalid
bridges.cpp:134:25: error: 'rollback' was not declared in this scope
134 | rollback(record);
| ^~~~~~~~