Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Make CSP great again
- //You're as beautiful as the day I lost you
- //New year, best wishes
- #include <bits/stdc++.h>
- #define TASK "TESTCODE"
- #define Log2(x) 31 - __builtin_clz(x)
- using namespace std;
- const int N = 1e5;
- map<pair<int, int>, vector<int> > Map;
- int n, q, a[N + 1], t[N + 1], x[N + 1], y[N + 1], lab[N + 1];
- bool res[N + 1];
- struct SegmentTree
- {
- int Tree[4 * N + 1];
- void BuildTree(int v, int TreeL, int TreeR)
- {
- if (TreeL == TreeR)
- {
- if (t[TreeL] == 1)
- {
- Tree[v] = a[TreeL];
- }
- else
- {
- Tree[v] = 0;
- }
- return ;
- }
- int mid = (TreeL + TreeR)/2;
- BuildTree(v * 2, TreeL, mid);
- BuildTree(v * 2 + 1, mid + 1, TreeR);
- Tree[v] = max(Tree[2 * v], Tree[2 * v + 1]);
- }
- void update(int v, int TreeL, int TreeR, int pos, int val)
- {
- if (TreeL == TreeR)
- {
- Tree[v] = val;
- return ;
- }
- int mid = (TreeL + TreeR)/2;
- if (pos <= mid)
- {
- update(v * 2, TreeL, mid, pos, val);
- }
- else
- {
- update(v * 2 + 1, mid + 1, TreeR, pos, val);
- }
- Tree[v] = max(Tree[2 * v], Tree[2 * v + 1]);
- }
- int query(int v, int TreeL, int TreeR, int R)
- {
- if (Tree[v] < R)
- {
- return -1;
- }
- if (TreeL == TreeR)
- {
- return TreeL;
- }
- int mid = (TreeL + TreeR)/2;
- int t = query(v * 2, TreeL, mid, R);
- if (t == -1)
- {
- t = query(v * 2 + 1, mid + 1, TreeR, R);
- }
- return t;
- }
- } Tree;
- void read()
- {
- cin >> n >> q;
- memset(lab, -1, sizeof(lab));
- for (int i = 1; i <= q; ++ i)
- {
- a[i] = q + 1;
- cin >> t[i] >> x[i] >> y[i];
- if (x[i] > y[i])
- {
- swap(x[i], y[i]);
- }
- if (t[i] == 1)
- {
- Map[ {x[i], y[i]}].push_back(i);
- }
- else if (t[i] == 2)
- {
- if (!Map[ {x[i], y[i]}].empty())
- {
- a[Map[ {x[i], y[i]}].back()] = i;
- Map[ {x[i], y[i]}].pop_back();
- }
- }
- }
- Tree.BuildTree(1, 1, q);
- }
- stack<tuple<int, int, int, int, int> > Stack;
- void Undo(int s)
- {
- while(Stack.size() > s)
- {
- int u, v, sz, i, k;
- tie(u, v, sz, i, k) = Stack.top();
- Stack.pop();
- Tree.update(1, 1, q, i, a[i]);
- if (k == 0)
- {
- continue;
- }
- lab[v] = -sz;
- lab[u] += sz;
- }
- }
- int FindSet(int u)
- {
- return lab[u] < 0 ? u : FindSet(lab[u]);
- }
- void Unite(int i)
- {
- int u = FindSet(x[i]);
- int v = FindSet(y[i]);
- Tree.update(1, 1, q, i, 0);
- if (u == v)
- {
- Stack.push(make_tuple(u, v, -lab[v], i, 0));
- return ;
- }
- if (lab[v] < lab[u])
- {
- swap(u, v);
- }
- Stack.push(make_tuple(u, v, -lab[v], i, 1));
- lab[u] += lab[v];
- lab[v] = u;
- }
- void Dnc(int L, int R)
- {
- if (L > R)
- {
- return ;
- }
- int s = Stack.size();
- while (true)
- {
- int i = Tree.query(1, 1, q, R);
- if (i == -1 || i > L)
- {
- break;
- }
- Unite(i);
- }
- if (L == R)
- {
- if (t[L] == 3)
- {
- int u = FindSet(x[L]), v = FindSet(y[L]);
- res[L] = (u == v);
- }
- Undo(s);
- return ;
- }
- int mid = (L + R)/2;
- Dnc(L, mid);
- Dnc(mid + 1, R);
- Undo(s);
- }
- void solve()
- {
- Dnc(1, q);
- for (int i = 1; i <= q; ++ i)
- {
- if (t[i] == 3)
- {
- cout << (res[i] ? "YES" : "NO") << '\n';
- }
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- if (fopen(TASK".INP", "r"))
- {
- freopen(TASK".INP", "r", stdin);
- //freopen(TASK".OUT", "w", stdout);
- }
- int t = 1;
- bool typetest = false;
- if (typetest)
- {
- cin >> t;
- }
- for (int __ = 1; __ <= t; ++ __)
- {
- //cout << "Case " << __ << ": ";
- read();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement