cpp_alex

Загадка ДО, почему не работает?

Aug 5th, 2021
864
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <functional>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6.  
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. template<typename T>
  12. using vc = std::vector<T>;
  13.  
  14. template<typename T>
  15. using mt = vc<vc<T>>;
  16.  
  17. struct segtree {
  18. private:
  19.     vc<ll> d;
  20.  
  21.     constexpr static ll neutral = 0;
  22.  
  23.     void build(const vc<ll>& a, ll v, ll tl, ll tr) {
  24.         if (tl == tr) {
  25.             d[v] = a[tl];
  26.         }
  27.         else {
  28.             ll mid = (tl + tr) / 2;
  29.  
  30.             build(a, v * 2, tl, mid);
  31.             build(a, v * 2 + 1, mid + 1, tr);
  32.  
  33.             d[v] = d[v * 2] + d[v * 2 + 1];
  34.         }
  35.     }
  36. public:
  37.  
  38.     segtree (const vc<ll>& na) : d(na.size() * 4) {
  39.         build(na, 1, 0, na.size() - 1);
  40.     }
  41.  
  42.     ll query (ll v, ll tl, ll tr, ll l, ll r) {
  43.         if (l > r) {
  44.             return neutral;
  45.         }
  46.  
  47.         if (l == tl && r == tr) {
  48.             return d[v];
  49.         }
  50.  
  51.         ll mid = (tl + tr) / 2;
  52.         return query(v * 2, tl, mid, l, std::min(r, mid)) + query(v * 2 + 1, mid + 1, tr, std::max(l, mid + 1), r);
  53.     }
  54.  
  55.     void update (ll i, ll x, ll v, ll tl, ll tr) {
  56.         if (tl == tr) {
  57.             d[v] = x;
  58.         }
  59.         else {
  60.             ll mid = (tl + tr) / 2;
  61.  
  62.             if (i <= mid) {
  63.                 update(i, x, v * 2, tl, mid);
  64.             }
  65.             else {
  66.                 update(i, x, v * 2 + 1, mid + 1, tr);
  67.             }
  68.             d[v] = d[v * 2] + d[v * 2 + 1];
  69.         }
  70.     }
  71.  
  72.     vc<ll> debug () {
  73.         return d;
  74.     }
  75. };
  76.  
  77. int main () {
  78.     ll n;
  79.  
  80.     std::cin >> n;
  81.  
  82.     vc<std::pair<ll, ll>> crd;
  83.     vc<char> type;
  84.  
  85.     ll a, b, c;
  86.     while (true) {
  87.         std::cin >> a;
  88.  
  89.         if (a == 0) {
  90.             break;
  91.         }
  92.         else {
  93.             std::cin >> b >> c;
  94.         }
  95.  
  96.         crd.push_back(std::make_pair(b, c));
  97.         type.push_back(a);
  98.     }
  99.  
  100.     segtree rsq(vc<ll>(n, 0));
  101.  
  102.     for (int i = 0; i < crd.size(); ++i) {
  103.         if (type[i] == 1) {
  104.             //rsq.update(crd[i].first - 1, crd[i].second);
  105.             rsq.update(crd[i].first - 1, crd[i].second, 1, 0, n - 1);
  106.         }
  107.         else {
  108.             //std::cout << "yes\n";
  109.             std::cout << rsq.query(1, 0, n - 1, crd[i].first - 1, crd[i].second - 1);
  110.             std::cout << " ";
  111.         }
  112.     }
  113.  
  114.     vc<ll> db = rsq.debug();
  115.  
  116.     std::cout << "\n";
  117.  
  118.     for (const auto& i : db) {
  119.         std::cout << i << " ";
  120.     }
  121.  
  122.     return 0;
  123. }
RAW Paste Data