Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int parent[200003], size[200003], maxi[200003];
- int parent2[200003], size2[200003], maxi2[200003];
- void perform() {
- for (int i = 0; i < 200003; i++) {
- parent[i] = i;
- size[i] = 1;
- maxi[i] = i;
- parent2[i] = i;
- size2[i] = 1;
- maxi2[i] = i;
- }
- }
- int get(int a) {
- if (parent[a] == a) return a;
- int x = a;
- while (a != parent[a]) {
- a = parent[a];
- }
- while (x != parent[x]) {
- int temp = parent[x];
- parent[x] = a;
- x = temp;
- }
- return a;
- }
- int get2(int a) {
- if (parent2[a] == a) return a;
- int x = a;
- while (a != parent2[a]) {
- a = parent2[a];
- }
- while (x != parent2[x]) {
- int temp = parent2[x];
- parent2[x] = a;
- x = temp;
- }
- return a;
- }
- void unioon(int a, int b) {
- a = get(a);
- b = get(b);
- if (a != b) {
- if (size[a] > size[b]) swap(b, a);
- parent[a] = b;
- size[b] += size[a];
- maxi[b] = max(maxi[a], maxi[b]);
- }
- }
- void unioon2(int a, int b) {
- a = get2(a);
- b = get2(b);
- if (a != b) {
- if (size2[a] > size2[b]) swap(b, a);
- parent2[a] = b;
- size2[b] += size2[a];
- maxi2[b] = max(maxi2[a], maxi2[b]);
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int m;
- cin >> m >> m;
- perform();
- int x, y, z;
- while (m--) {
- cin >> x >> y >> z;
- if (x == 1) unioon(y, z);
- if (x == 2) {
- int p = maxi2[y];
- while (p < z) {
- unioon(p, z);
- unioon2(p, p + 1);
- p = maxi2[p + 1];
- }
- unioon2(y, z);
- }
- if (x == 3) {
- int ans = (get(y) == get(z));
- if (ans) cout << "YES\n";
- else cout << "NO\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement