Advertisement
konchin_shih

ZJ b412

Jan 28th, 2023
646
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.90 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<functional>
  4. #define endl '\n'
  5. using namespace std;
  6. template<typename T>
  7. struct segment {
  8.     int size;
  9.     struct node {
  10.         T v; node *l, *r;
  11.         node() {l = r = nullptr;}
  12.         node(T x): v(x) {l = r = nullptr;}
  13.     }*root;
  14.     operator bool() {return size;}
  15.     node* build(const vector<T>& arr, int l, int r) {
  16.         if (l == r) {return new node(arr[l - 1]);}
  17.         node* ret = new node;
  18.         int m = (l + r) >> 1;
  19.         ret->l = build(arr, l    , m);
  20.         ret->r = build(arr, m + 1, r);
  21.         return ret;
  22.     }
  23.     void build(const vector<T>& arr) {root = build(arr, 1, size);}
  24.     node* update(int i, T k, int l, int r, node* pre) {
  25.         if (r < i || i < l) return pre;
  26.         if (l == r) return new node(k);
  27.         node* ret = new node;
  28.         int m = (l + r) >> 1;
  29.         ret->l = update(i, k, l    , m, pre->l);
  30.         ret->r = update(i, k, m + 1, r, pre->r);
  31.         return ret;
  32.     }
  33.     void update(int i, T k) {
  34.         root = update(i, k, 1, size, root);
  35.     }
  36.     T at(int i, int l, int r, node* cur) {
  37.         if (l == r) return cur->v;
  38.         int m = (l + r) >> 1;
  39.         if (i <= m) return at(i, l, m, cur->l);
  40.         else return at(i, m + 1, r, cur->r);
  41.     }
  42.     T at(int i) {return at(i, 1, size, root);}
  43.     segment(const vector<T>& arr): size(arr.size()) {build(arr);}
  44.     segment(int s): size(s), root(nullptr) {}
  45. };
  46.  
  47. int main() {
  48.     cin.tie(nullptr);
  49.     ios::sync_with_stdio(false);
  50.     int n, m; cin >> n >> m;
  51.     vector<segment<pair<int, int>>> v(m + 1, n);
  52.     vector<pair<int, int>> tmp(n);
  53.     for (int i = 0; i != n; i++)
  54.         tmp[i] = {i + 1, 1};
  55.     v[0].build(tmp);
  56.     function<pair<int, int>(int, segment<pair<int, int>>&)> find = [&find](int i, segment<pair<int, int>>& cur) {
  57.         pair<int, int> tmp = cur.at(i);
  58.         return i == tmp.first ? tmp : find(tmp.first, cur);
  59.     };
  60.     function<void(int, int, segment<pair<int, int>>&)> join = [&find](int a, int b, segment<pair<int, int>>& cur) {
  61.         auto x = find(a, cur), y = find(b, cur);
  62.         auto cmp = [](pair<int, int> a, pair<int, int> b) {return a.second < b.second || (a.second == b.second && a.first < b.first);};
  63.         auto maxn = max(x, y, cmp), minn = min(x, y, cmp);
  64.         cur.update(minn.first, {maxn.first, minn.second});
  65.         cur.update(maxn.first, {maxn.first, maxn.second + minn.second});
  66.     };
  67.     for (int i = 1, op, x, y, k, ans = 0; i <= m; i++) {
  68.         cin >> op, op ^= ans;
  69. //      cout << "op: " << op << endl;
  70.         switch (op) {
  71.         case 0:
  72.             cin >> k, k ^= ans;
  73. //          cout << "k: " << k << endl;
  74.             v[i] = v[k];
  75.             break;
  76.         case 1:
  77.             cin >> x >> y, x ^= ans, y ^= ans;
  78. //          cout << "xy: " << x << ' ' << y << endl;
  79.             v[i] = v[i - 1];
  80.             join(x, y, v[i]);
  81.             break;
  82.         case 2:
  83.             cin >> x >> y, x ^= ans, y ^= ans;
  84. //          cout << "xy: " << x << ' ' << y << endl;
  85.             v[i] = v[i - 1];
  86.             auto a = find(x, v[i]), b = find(y, v[i]);
  87. //          cout << "a: " << a.first << ' ' << a.second << endl;
  88. //          cout << "b: " << b.first << ' ' << b.second << endl;
  89.             ans = (a.first == b.first);
  90.             cout << ans << endl;
  91.             break;
  92.         }
  93.     }
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement