Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#pragma GCC optimize("Ofast")
- using namespace std;
- typedef long long ll;
- #ifdef ONPC
- mt19937 rnd(228);
- #else
- mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
- #endif
- const int BLOCK = 1100;
- const int N = 1e5 + 7;
- int dsu[N];
- int sz[N];
- bool bad[N];
- int ind[N];
- int w[N];
- int u[N], v[N];
- inline int get(int v)
- {
- if (v == dsu[v])
- {
- return v;
- }
- else
- {
- return dsu[v] = get(dsu[v]);
- }
- }
- inline void uni(int u, int v)
- {
- u = get(u), v = get(v);
- if (u == v) return;
- if (sz[u] > sz[v]) swap(u, v);
- dsu[u] = v;
- sz[v] += sz[u];
- }
- int gays[N];
- int spanning[N];
- int was_id[N];
- int par[N];
- bool vis[N];
- int ans[N];
- vector <int> events[N];
- vector <pair <int, int> > gr[N];
- int predok[N];
- bool flex[N];
- int microdsu[N];
- int microsz[N];
- int micrornk[N];
- inline int microget(int v)
- {
- if (v == microdsu[v])
- {
- return v;
- }
- else
- {
- return microdsu[v] = microget(microdsu[v]);
- }
- }
- inline void microuni(int u, int v)
- {
- u = microget(u);
- v = microget(v);
- if (u == v) return;
- if (micrornk[u] > micrornk[v]) swap(u, v);
- if (micrornk[u] ==micrornk[v]) micrornk[v]++;
- microsz[v] += microsz[u];
- microdsu[u] = v;
- }
- int main()
- {
- #ifdef ONPC
- freopen("a.in", "r", stdin);
- #endif
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n = 50000, m = 49999;
- int inf = 1e9;
- cin >> n >> m;
- for (int i = 0; i < n; i++)
- {
- microdsu[i] = i;
- microsz[i] = 1;
- }
- for (int i = 0; i < m; i++)
- {
- u[i] = rnd() % n, v[i] = rnd() % n;
- w[i] = rnd() % inf;
- cin >> u[i] >> v[i] >> w[i];
- u[i]--, v[i]--;
- ind[i] = i;
- w[i] *= -1;
- }
- int q = 100000;
- cin >> q;
- vector <int> t(q), a(q), b(q);
- for (int i = 0; i < q; i++)
- {
- cin >> t[i] >> a[i] >> b[i];
- a[i]--;
- // t[i] = rnd() % 2 + 1;
- //t[i] = rnd() % 2 + 1;
- //a[i] = rnd() % n;
- //b[i] = rnd() % inf;
- //a[i]--;
- b[i] *= -1;
- }
- //for (int i = 0; i < q; i++) events[i].reserve(2 * BLOCK);
- for (int i = 0; i < n; i++)
- {
- dsu[i] = i;
- sz[i] = 1;
- }
- set <pair <int, int> > glob;
- for (int i = 0; i < m; i++)
- {
- glob.insert({w[i], i});
- }
- vector <pair <int, int> > e;
- int sum = 0;
- for (int i = 0; i < q; i += BLOCK)
- {
- for (int i = 0; i < m; i++) bad[i] = 0, flex[i] = 0;
- int l = i, r = min(q, i + BLOCK);
- for (int ptr = l; ptr < r; ptr++)
- {
- if (t[ptr] == 1)
- {
- glob.erase({w[a[ptr]], a[ptr]});
- bad[a[ptr]] = 1;
- }
- }
- for (int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
- double was = clock();
- auto it = glob.begin();
- for (auto &c : glob)
- {
- int id = c.second;
- if (get(u[id]) != get(v[id]))
- {
- uni(u[id], v[id]);
- flex[id] = true;
- }
- }
- double now = clock();
- for (int i = 0; i < n; i++) dsu[i] = i,sz[i] = 1;
- set <pair <int, int> > q;
- for (int ptr = l; ptr < r; ptr++)
- {
- if (t[ptr] == 1)
- {
- glob.insert({-inf, a[ptr]});
- }
- }
- int span_len = 0;
- for (auto &c : glob)
- {
- int id = c.second;
- if (get(u[id]) != get(v[id]))
- {
- uni(u[id], v[id]);
- flex[id] = false;
- if (!bad[id])
- {
- spanning[span_len++] = id;
- }
- }
- }
- for (int ptr = l; ptr < r; ptr++)
- {
- if (t[ptr] == 1)
- {
- glob.erase({-inf, a[ptr]});
- }
- }
- for (int ptr = l; ptr < r; ptr++)
- {
- if (t[ptr] == 1)
- {
- glob.insert({w[a[ptr]], a[ptr]});
- }
- }
- for (int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
- for (int i = 0; i < m; i++)
- {
- if (bad[i] || flex[i])
- {
- q.insert({w[i], i});
- sum++;
- }
- }
- e.clear();
- for (int ptr = l; ptr < r; ptr++)
- {
- if (t[ptr] == 1)
- {
- glob.erase({w[a[ptr]], a[ptr]});
- q.erase({w[a[ptr]], a[ptr]});
- w[a[ptr]] = b[ptr];
- q.insert({w[a[ptr]], a[ptr]});
- glob.insert({w[a[ptr]], a[ptr]});
- }
- else
- {
- for (auto &c : q)
- {
- if (c.first > b[ptr]) break;
- events[ptr].push_back(c.second);
- }
- e.push_back({b[ptr], ptr});
- }
- }
- sort(e.begin(), e.end());
- for (int i = 0; i < n; i++)
- {
- dsu[i] = i;
- sz[i] = 1;
- }
- int _st = -1;
- for (int i = 0; i <= span_len; i++)
- {
- while (_st + 1 < (int) e.size() && (i == span_len || e[_st + 1].first < w[spanning[i]]))
- {
- _st++;
- int id = e[_st].second;
- micrornk[get(a[id])] = 1;
- microsz[get(a[id])] = sz[get(a[id])];
- microdsu[get(a[id])] = get(a[id]);
- for (int x : events[id])
- {
- int l = get(u[x]);
- micrornk[l] = 1;
- microdsu[l] = l;
- microsz[l] = sz[l];
- l = get(v[x]);
- micrornk[l] = 1;
- microdsu[l] = l;
- microsz[l] = sz[l];
- }
- for (int x : events[id])
- {
- sum++;
- microuni(get(u[x]), get(v[x]));
- }
- ans[id] = microsz[microget(get(a[id]))];
- }
- if (i == span_len) break;
- uni(u[spanning[i]], v[spanning[i]]);
- }
- }
- for (int i = 0; i < q; i++)
- {
- if (t[i] == 2)
- {
- cout << ans[i] << '\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement