Advertisement
maycod23

segtree

Jun 25th, 2022
660
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.26 KB | None
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define ll long long
  4. #define all(x) x.begin(), x.end()
  5.  
  6. const ll INF = 2e18;
  7. const ll mod = 1000000007;
  8. const ll maxn = 1e5 + 5;
  9.  
  10. template <typename node, typename update>
  11. struct segTree {
  12.     ll len;
  13.     vector<node> t;
  14.     vector<update> u;
  15.     vector<bool> lazy;
  16.     vector<ll> tl, tr;
  17.     node identity_element;
  18.     update identity_transformation;
  19.  
  20.     template<typename T>
  21.     segTree(T &a) {
  22.         len = a.size();
  23.         t.resize(4 * len);
  24.         u.resize(4 * len);
  25.         lazy.resize(4 * len);
  26.         tl.resize(4 * len);
  27.         tr.resize(4 * len);
  28.         identity_element = node();
  29.         identity_transformation = update();
  30.         build(a, 1, 0, len - 1);
  31.     }
  32.  
  33.     template <typename T>
  34.     void build(const T &a, const ll &v, const ll &l, const ll &r) {
  35.         tl[v] = l;
  36.         tr[v] = r;
  37.         if (l == r) {
  38.             t[v] = a[l];
  39.             return;
  40.         }
  41.         ll tm = (l + r) >> 1;
  42.         build(a, v << 1, l, tm);
  43.         build(a, v << 1 | 1, tm + 1, r);
  44.         t[v].merge(t[v << 1], t[v << 1 | 1]);
  45.     }
  46.  
  47.     void apply(const ll &v, update val) {
  48.         if (tl[v] != tr[v]) {
  49.             lazy[v] = 1;
  50.             u[v].combine(val, tl[v], tr[v]);
  51.         }
  52.         val.apply(t[v], tl[v], tr[v]);
  53.     }
  54.  
  55.     void pushdown(const ll &v) {
  56.         if (lazy[v]) {
  57.             apply(v << 1, u[v]);
  58.             apply(v << 1 | 1, u[v]);
  59.             u[v] = identity_transformation;
  60.             lazy[v] = 0;
  61.         }
  62.     }
  63.  
  64.     void rupd(const ll &v, const ll &l, const ll &r, update val) {
  65.         if (l > tr[v] || r < tl[v])
  66.             return;
  67.         if (tl[v] >= l && tr[v] <= r) {
  68.             apply(v, val);
  69.             return;
  70.         }
  71.         pushdown(v);
  72.         rupd(v << 1, l, r, val);
  73.         rupd(v << 1 | 1, l, r, val);
  74.         t[v].merge(t[v << 1], t[v << 1 | 1]);
  75.     }
  76.  
  77.     node query(const ll &v, const ll &l, const ll &r) {
  78.         if (l > tr[v] || r < tl[v])
  79.             return identity_element;
  80.         if (tl[v] >= l && tr[v] <= r)
  81.             return t[v];
  82.         pushdown(v);
  83.         node a, b, ans;
  84.         a = query(v * 2, l, r);
  85.         b = query(v * 2 + 1, l, r);
  86.         ans.merge(a, b);
  87.         return ans;
  88.     }
  89.  
  90.     node query(const ll &l, const ll &r) {
  91.         return query(1, l, r);
  92.     }
  93.     void rupd(const ll &l, const ll &r, update upd) {
  94.         rupd(1, l, r, upd);
  95.     }
  96. };
  97.  
  98. struct node1 {
  99.     ll sum = 0;
  100.     map<ll, ll> mp;
  101.     node1() {}
  102.     node1(ll val) {
  103.         sum = val;
  104.         mp[val]++;
  105.     }
  106.     void merge(const node1 &l, const node1 &r) {
  107.         sum = l.sum + r.sum;
  108.         for (auto &i : l.mp) {
  109.             mp[i.first] += i.second;
  110.         }
  111.         for (auto &j : r.mp) {
  112.             mp[j.first] += j.second;
  113.         }
  114.     }
  115.     bool check(ll x) {
  116.         return false;
  117.     }
  118. };
  119. struct update1 {
  120.     ll v = 0;
  121.  
  122.     update1() {}
  123.     update1(ll val) {
  124.         v = val;
  125.     }
  126.     void combine(update1 &other, const ll &tl, const ll &tr) {
  127.     }
  128.     void apply(node1 &x, const ll &tl, const ll &tr) {
  129.         x.mp[x.sum]--;
  130.         if (x.mp[x.sum] == 0) x.mp.erase(x.sum);
  131.         x.sum = v;
  132.         x.mp[x.sum]++;
  133.     }
  134. };
  135.  
  136. void solve() {
  137.     ll n;
  138.     cin >> n;
  139.     ll q;
  140.     cin >> q;
  141.     vector<ll> a(n + 5);
  142.     for (ll i = 1; i <= n; i++)    cin >> a[i];
  143.     segTree<node1, update1> st(a);
  144.     while (q--) {
  145.         ll t;
  146.         cin >> t;
  147.         if (t == 1) {
  148.             ll i, v;
  149.             cin >> i >> v;
  150.             st.rupd(i, i, v);
  151.         } else {
  152.             ll l, r;
  153.             cin >> l >> r;
  154.             auto mp = st.query(l, r).mp;
  155.             ll ans = 0;
  156.             for (auto &i : mp) {
  157.                 ans += (i.second & 1);
  158.             }
  159.             cout << ans << ' ';
  160.         }
  161.     }
  162. }
  163.  
  164. signed main() {
  165.     ios_base::sync_with_stdio(false), cin.tie(nullptr);
  166.     int t;
  167.     cin >> t;
  168.     for (int i = 1; i <= t; i++) {
  169.         solve();
  170.     }
  171.     return 0;
  172. }
Advertisement
RAW Paste Data Copied
Advertisement