Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ull = unsigned long long;
- using ui = unsigned int;
- using ld = long double;
- using pii = pair<int, int>;
- using pil = pair<int, long long>;
- using pli = pair<long long, int>;
- using pll = pair<long long, long long>;
- template <typename T>
- using uset = unordered_set<T>;
- template <typename T1, typename T2>
- using umap = unordered_map<T1, T2>;
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #ifndef _DEBUG
- #pragma GCC optimize("O3,unroll-loops,fast-math")
- #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
- #endif
- struct info {
- int b, x, len;
- info() {}
- info(int b, int x, int len): b(b), x(x), len(len) {}
- };
- vector<info> or_merge(const vector<info> &a, const vector<info> &b) {
- if (a.empty())
- return b;
- if (b.empty())
- return a;
- vector<info> res;
- int n = a.size(), m = b.size();
- int i = 0, j = 0;
- int cur_or = 0;
- while (i < n && j < m) {
- if (a[i].x <= b[j].x) {
- cur_or |= a[i].b;
- if (res.empty() || res.back().b < cur_or)
- res.push_back({cur_or, a[i].x, a[i].len});
- else
- res.back().len += a[i].len;
- i++;
- } else {
- cur_or |= b[j].b;
- if (res.empty() || res.back().b < cur_or)
- res.push_back({cur_or, b[j].x, b[j].len});
- else
- res.back().len += b[j].len;
- j++;
- }
- }
- while (i < n) {
- cur_or |= a[i].b;
- if (res.empty() || res.back().b < cur_or)
- res.push_back({cur_or, a[i].x, a[i].len});
- else
- res.back().len += a[i].len;
- i++;
- }
- while (j < m) {
- cur_or |= b[j].b;
- if (res.empty() || res.back().b < cur_or)
- res.push_back({cur_or, b[j].x, b[j].len});
- else
- res.back().len += b[j].len;
- j++;
- }
- return res;
- }
- vector<info> and_merge(const vector<info> &a, const vector<info> &b) {
- if (a.empty())
- return b;
- if (b.empty())
- return a;
- vector<info> res;
- int n = a.size(), m = b.size();
- int i = 0, j = 0;
- int cur_and = (1 << 20) - 1;
- while (i < n && j < m) {
- if (a[i].x >= b[j].x) {
- cur_and &= a[i].b;
- if (res.empty() || res.back().b > cur_and)
- res.push_back({cur_and, a[i].x, a[i].len});
- else
- res.back().len += a[i].len;
- i++;
- } else {
- cur_and &= b[j].b;
- if (res.empty() || res.back().b > cur_and)
- res.push_back({cur_and, b[j].x, b[j].len});
- else
- res.back().len += b[j].len;
- j++;
- }
- }
- while (i < n) {
- cur_and &= a[i].b;
- if (res.empty() || res.back().b > cur_and)
- res.push_back({cur_and, a[i].x, a[i].len});
- else
- res.back().len += a[i].len;
- i++;
- }
- while (j < m) {
- cur_and &= b[j].b;
- if (res.empty() || res.back().b > cur_and)
- res.push_back({cur_and, b[j].x, b[j].len});
- else
- res.back().len += b[j].len;
- j++;
- }
- return res;
- }
- struct node {
- vector<info> _or, _and;
- node() {}
- node(int x) {
- info i(x, x, 1);
- _or.push_back(i);
- _and.push_back(i);
- }
- };
- node merge(const node &a, const node &b) {
- node res;
- res._or = or_merge(a._or, b._or);
- res._and = and_merge(a._and, b._and);
- return res;
- }
- struct segtree {
- vector<node> tree;
- int sz;
- segtree() {}
- void build(int v, int tl, int tr, const vector<int> &a) {
- if (tr - tl == 1) {
- tree[v] = a[tl];
- return;
- }
- int m = (tl + tr) / 2;
- build(2 * v + 1, tl, m, a);
- build(2 * v + 2, m, tr, a);
- tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
- }
- segtree(const vector<int> &a) {
- sz = a.size();
- tree.resize(4 * sz);
- build(0,0, sz, a);
- }
- void set(int i, int x, int v, int tl, int tr) {
- if (tr - tl == 1) {
- tree[v] = x;
- return;
- }
- int m = (tl + tr) / 2;
- if (i < m)
- set(i, x, 2 * v + 1, tl, m);
- else
- set(i, x, 2 * v + 2, m ,tr);
- tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
- }
- void set(int i, int x) {
- set(i, x, 0, 0, sz);
- }
- node get(int l, int r, int v, int tl, int tr) {
- if (l <= tl && tr <= r)
- return tree[v];
- int m = (tl + tr) / 2;
- if (r <= m)
- return get(l, r, 2 * v + 1, tl, m);
- if (l >= m)
- return get(l, r, 2 * v + 2, m, tr);
- node s1, s2;
- s1 = get(l, r, 2 * v + 1, tl ,m);
- s2 = get(l, r, 2 * v + 2, m, tr);
- return merge(s1, s2);
- }
- node get(int l, int r) {
- return get(l, r, 0,0 , sz);
- }
- };
- inline void solve() {
- int n, queries;
- cin >> n >> queries;
- vector<int> a(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- segtree st(a);
- auto intersect = [&](int l1, int r1, int l2, int r2) -> int {
- int mxl = max(l1, l2);
- int mnr = min(r1, r2);
- return max(0, mnr - mxl);
- };
- while (queries--) {
- int t, l, r;
- cin >> t >> l >> r;
- l--;
- r--;
- if (t == 1) {
- if (l != r) {
- st.set(l, a[r]);
- st.set(r, a[l]);
- }
- swap(a[l], a[r]);
- continue;
- }
- node seg = st.get(l, r + 1);
- int ans = 0;
- int szi = seg._or.size();
- int szj = seg._and.size();
- int i = 0, j = szj - 1;
- int leni = 0, lenj = 0;
- while (i < szi && j >= 0) {
- int l1 = leni, r1 = leni + seg._or[i].len;
- int l2 = lenj, r2 = lenj + seg._and[j].len;
- if (seg._or[i].b == seg._and[j].b)
- ans += intersect(l1, r1, l2, r2);
- if (r1 <= r2) {
- leni += seg._or[i].len;
- i++;
- } else {
- lenj += seg._and[j].len;
- j--;
- }
- }
- cout << ans << '\n';
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("01.dat", "r", stdin);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int tt = 1;
- #ifdef _DEBUG
- cin >> tt;
- #endif
- for (int test_id = 1; test_id <= tt; test_id++) {
- #ifdef _DEBUG
- cout << "TESTCASE #" << test_id << ":\n";
- #endif
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment