Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define REP(i, n) for(int i = 0;i < n;++i)
- #define FOR(i, a, b) for(int i = a;i < b;++i)
- #define pb push_back
- using namespace std;
- const int MAX = 1 << 19;
- const int offset = 1 << 18;
- bool vis[MAX];
- int root[MAX];
- int get_(int x) { return x == root[x] ? x : root[x] = get_(root[x]); }
- void union_(int a, int b) {
- if(rand() % 2) swap(a, b);
- root[get_(a)] = get_(b);
- }
- void update(int x, int lo, int hi, int l, int r) {
- if(hi <= l || lo >= r) return;
- if(lo + 1 == hi) {
- union_(l, x);
- vis[x] = true;
- return;
- }
- int mid = (lo + hi) / 2;
- if(lo >= l && hi <= r) {
- union_(l, x);
- if(!vis[2 * x]) update(2 * x, lo, mid, l, r);
- else union_(2 * x, l);
- if(!vis[2 * x + 1]) update(2 * x + 1, mid, hi, l, r);
- else union_(2 * x + 1, l);
- vis[x] = true;
- return;
- }
- update(2 * x, lo, mid, l, r), update(2 * x + 1, mid, hi, l, r);
- }
- int main() {
- srand(time(NULL));
- int n, q;
- REP(i, MAX) root[i] = i;
- scanf("%d%d", &n, &q);
- int type, a, b;
- REP(i, q) {
- scanf("%d%d%d", &type, &a, &b);
- if(type == 1) union_(a + offset - 1, b + offset - 1);
- else if(type == 2) update(1, offset, 2 * offset, a + offset - 1, b + offset);
- else if(get_(a + offset - 1) == get_(b + offset - 1)) printf("YES\n");
- else printf("NO\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement