Advertisement
Guest User

Untitled

a guest
Jul 31st, 2015
690
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define REP(i, n) for(int i = 0;i < n;++i)
  3. #define FOR(i, a, b) for(int i = a;i < b;++i)
  4. #define pb push_back
  5. using namespace std;
  6. const int MAX = 1 << 19;
  7. const int offset = 1 << 18;
  8. bool vis[MAX];
  9. int root[MAX];
  10.  
  11. int get_(int x) { return x == root[x] ? x : root[x] = get_(root[x]); }
  12.  
  13. void union_(int a, int b) {
  14.     if(rand() % 2) swap(a, b);
  15.     root[get_(a)] = get_(b);
  16. }
  17.  
  18. void update(int x, int lo, int hi, int l, int r) {
  19.     if(hi <= l || lo >= r) return;
  20.     if(lo + 1 == hi) {
  21.         union_(l, x);
  22.         vis[x] = true;
  23.         return;
  24.     }
  25.     int mid = (lo + hi) / 2;
  26.     if(lo >= l && hi <= r) {
  27.         union_(l, x);
  28.         if(!vis[2 * x]) update(2 * x, lo, mid, l, r);
  29.         else union_(2 * x, l);
  30.         if(!vis[2 * x + 1]) update(2 * x + 1, mid, hi, l, r);
  31.         else union_(2 * x + 1, l);
  32.         vis[x] = true;
  33.         return;
  34.     }
  35.     update(2 * x, lo, mid, l, r), update(2 * x + 1, mid, hi, l, r);
  36. }
  37.  
  38. int main() {
  39.     srand(time(NULL));
  40.     int n, q;
  41.     REP(i, MAX) root[i] = i;
  42.     scanf("%d%d", &n, &q);
  43.     int type, a, b;
  44.     REP(i, q) {
  45.         scanf("%d%d%d", &type, &a, &b);
  46.         if(type == 1) union_(a + offset - 1, b + offset - 1);
  47.         else if(type == 2) update(1, offset, 2 * offset, a + offset - 1, b + offset);
  48.         else if(get_(a + offset - 1) == get_(b + offset - 1)) printf("YES\n");
  49.         else printf("NO\n");
  50.     }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement