Guest User

Untitled

a guest
Jul 6th, 2025
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ull = unsigned long long;
  7. using ui = unsigned int;
  8. using ld = long double;
  9. using pii = pair<int, int>;
  10. using pil = pair<int, long long>;
  11. using pli = pair<long long, int>;
  12. using pll = pair<long long, long long>;
  13. template <typename T>
  14. using uset = unordered_set<T>;
  15. template <typename T1, typename T2>
  16. using umap = unordered_map<T1, T2>;
  17.  
  18. #define all(x) x.begin(), x.end()
  19. #define rall(x) x.rbegin(), x.rend()
  20.  
  21. #ifndef _DEBUG
  22. #pragma GCC optimize("O3,unroll-loops,fast-math")
  23. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  24. #endif
  25.  
  26. struct info {
  27.     int b, x, len;
  28.  
  29.     info() {}
  30.  
  31.     info(int b, int x, int len): b(b), x(x), len(len) {}
  32. };
  33.  
  34. vector<info> or_merge(const vector<info> &a, const vector<info> &b) {
  35.     if (a.empty())
  36.         return b;
  37.     if (b.empty())
  38.         return a;
  39.     vector<info> res;
  40.     int n = a.size(), m = b.size();
  41.     int i = 0, j = 0;
  42.     int cur_or = 0;
  43.     while (i < n && j < m) {
  44.         if (a[i].x <= b[j].x) {
  45.             cur_or |= a[i].b;
  46.             if (res.empty() || res.back().b < cur_or)
  47.                 res.push_back({cur_or, a[i].x, a[i].len});
  48.             else
  49.                 res.back().len += a[i].len;
  50.             i++;
  51.         } else {
  52.             cur_or |= b[j].b;
  53.             if (res.empty() || res.back().b < cur_or)
  54.                 res.push_back({cur_or, b[j].x, b[j].len});
  55.             else
  56.                 res.back().len += b[j].len;
  57.             j++;
  58.         }
  59.     }
  60.     while (i < n) {
  61.         cur_or |= a[i].b;
  62.         if (res.empty() || res.back().b < cur_or)
  63.             res.push_back({cur_or, a[i].x, a[i].len});
  64.         else
  65.             res.back().len += a[i].len;
  66.         i++;
  67.     }
  68.     while (j < m) {
  69.         cur_or |= b[j].b;
  70.         if (res.empty() || res.back().b < cur_or)
  71.             res.push_back({cur_or, b[j].x, b[j].len});
  72.         else
  73.             res.back().len += b[j].len;
  74.         j++;
  75.     }
  76.     return res;
  77. }
  78.  
  79. vector<info> and_merge(const vector<info> &a, const vector<info> &b) {
  80.     if (a.empty())
  81.         return b;
  82.     if (b.empty())
  83.         return a;
  84.     vector<info> res;
  85.     int n = a.size(), m = b.size();
  86.     int i = 0, j = 0;
  87.     int cur_and = (1 << 20) - 1;
  88.     while (i < n && j < m) {
  89.         if (a[i].x >= b[j].x) {
  90.             cur_and &= a[i].b;
  91.             if (res.empty() || res.back().b > cur_and)
  92.                 res.push_back({cur_and, a[i].x, a[i].len});
  93.             else
  94.                 res.back().len += a[i].len;
  95.             i++;
  96.         } else {
  97.             cur_and &= b[j].b;
  98.             if (res.empty() || res.back().b > cur_and)
  99.                 res.push_back({cur_and, b[j].x, b[j].len});
  100.             else
  101.                 res.back().len += b[j].len;
  102.             j++;
  103.         }
  104.     }
  105.     while (i < n) {
  106.         cur_and &= a[i].b;
  107.         if (res.empty() || res.back().b > cur_and)
  108.             res.push_back({cur_and, a[i].x, a[i].len});
  109.         else
  110.             res.back().len += a[i].len;
  111.         i++;
  112.     }
  113.     while (j < m) {
  114.         cur_and &= b[j].b;
  115.         if (res.empty() || res.back().b > cur_and)
  116.             res.push_back({cur_and, b[j].x, b[j].len});
  117.         else
  118.             res.back().len += b[j].len;
  119.         j++;
  120.     }
  121.     return res;
  122. }
  123.  
  124. struct node {
  125.     vector<info> _or, _and;
  126.  
  127.     node() {}
  128.  
  129.     node(int x) {
  130.         info i(x, x, 1);
  131.         _or.push_back(i);
  132.         _and.push_back(i);
  133.     }
  134. };
  135.  
  136. node merge(const node &a, const node &b) {
  137.     node res;
  138.     res._or = or_merge(a._or, b._or);
  139.     res._and = and_merge(a._and, b._and);
  140.     return res;
  141. }
  142.  
  143. struct segtree {
  144.  
  145.     vector<node> tree;
  146.     int sz;
  147.  
  148.     segtree() {}
  149.  
  150.     void build(int v, int tl, int tr, const vector<int> &a) {
  151.         if (tr - tl == 1) {
  152.             tree[v] = a[tl];
  153.             return;
  154.         }
  155.         int m = (tl + tr) / 2;
  156.         build(2 * v + 1, tl, m, a);
  157.         build(2 * v + 2, m, tr, a);
  158.         tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
  159.     }
  160.  
  161.     segtree(const vector<int> &a) {
  162.         sz = a.size();
  163.         tree.resize(4 * sz);
  164.         build(0,0, sz, a);
  165.     }
  166.  
  167.     void set(int i, int x, int v, int tl, int tr) {
  168.         if (tr - tl == 1) {
  169.             tree[v] = x;
  170.             return;
  171.         }
  172.         int m = (tl + tr) / 2;
  173.         if (i < m)
  174.             set(i, x, 2 * v + 1, tl, m);
  175.         else
  176.             set(i, x, 2 * v + 2, m ,tr);
  177.         tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
  178.     }
  179.  
  180.     void set(int i, int x) {
  181.         set(i, x, 0, 0, sz);
  182.     }
  183.  
  184.     node get(int l, int r, int v, int tl, int tr) {
  185.         if (l <= tl && tr <= r)
  186.             return tree[v];
  187.         int m = (tl + tr) / 2;
  188.         if (r <= m)
  189.             return get(l, r, 2 * v + 1, tl, m);
  190.         if (l >= m)
  191.             return get(l, r, 2 * v + 2, m, tr);
  192.         node s1, s2;
  193.         s1 = get(l, r, 2 * v  + 1, tl ,m);
  194.         s2 = get(l, r, 2 * v + 2, m, tr);
  195.         return merge(s1, s2);
  196.     }
  197.  
  198.     node get(int l, int r) {
  199.         return get(l, r, 0,0 , sz);
  200.     }
  201. };
  202.  
  203. inline void solve() {
  204.     int n, queries;
  205.     cin >> n >> queries;
  206.     vector<int> a(n);
  207.     for (int i = 0; i < n; i++)
  208.         cin >> a[i];
  209.     segtree st(a);
  210.     auto intersect = [&](int l1, int r1, int l2, int r2) -> int {
  211.         int mxl = max(l1, l2);
  212.         int mnr = min(r1, r2);
  213.         return max(0, mnr - mxl);
  214.     };
  215.     while (queries--) {
  216.         int t, l, r;
  217.         cin >> t >> l >> r;
  218.         l--;
  219.         r--;
  220.         if (t == 1) {
  221.             if (l != r) {
  222.                 st.set(l, a[r]);
  223.                 st.set(r, a[l]);
  224.             }
  225.             swap(a[l], a[r]);
  226.             continue;
  227.         }
  228.         node seg = st.get(l, r + 1);
  229.         int ans = 0;
  230.         int szi = seg._or.size();
  231.         int szj = seg._and.size();
  232.         int i = 0, j = szj - 1;
  233.         int leni = 0, lenj = 0;
  234.         while (i < szi && j >= 0) {
  235.             int l1 = leni, r1 = leni + seg._or[i].len;
  236.             int l2 = lenj, r2 = lenj + seg._and[j].len;
  237.             if (seg._or[i].b == seg._and[j].b)
  238.                 ans += intersect(l1, r1, l2, r2);
  239.             if (r1 <= r2) {
  240.                 leni += seg._or[i].len;
  241.                 i++;
  242.             } else {
  243.                 lenj += seg._and[j].len;
  244.                 j--;
  245.             }
  246.         }
  247.         cout << ans << '\n';
  248.     }
  249. }
  250.  
  251. signed main() {
  252. #ifdef _DEBUG
  253.     freopen("01.dat", "r", stdin);
  254. #endif
  255.     ios_base::sync_with_stdio(false);
  256.     cin.tie(nullptr);
  257.     cout.tie(nullptr);
  258.     int tt = 1;
  259. #ifdef _DEBUG
  260.     cin >> tt;
  261. #endif
  262.     for (int test_id = 1; test_id <= tt; test_id++) {
  263. #ifdef _DEBUG
  264.         cout << "TESTCASE #" << test_id << ":\n";
  265. #endif
  266.         solve();
  267.     }
  268.     return 0;
  269. }
  270.  
Advertisement
Add Comment
Please, Sign In to add comment