SHARE
TWEET

xd

a guest Aug 21st, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. template<typename T>
  6. struct tree {
  7.     int n = 1;
  8.     int s;
  9.     vector<T> elements;
  10.     tree(int _n){
  11.         while (n < _n){
  12.             n *= 2;
  13.         }
  14.         n*=2;
  15.         elements.resize(n);
  16.         n /= 2;
  17.     }
  18.     void add(int a, int b, int l, int r, int i, T toadd){
  19.         if (a <= l and r <= b){
  20.             elements[i] += toadd;
  21.             return;
  22.         }
  23.         int mid = (l+r)/2;
  24.         if (a <= mid) add(a, b, l, mid, 2*i, toadd);
  25.         if (mid + 1 <= b) add(a, b, mid + 1, r, 2*i+1, toadd);
  26.         return;
  27.     }
  28.     T read(int i){
  29.         i += n;
  30.         T result = 0;
  31.         while (i != 0){
  32.             result += elements[i];
  33.             i/=2;
  34.         }
  35.         return result;
  36.     }
  37.     void print(){
  38.         int i = 1;
  39.         int m = 1;
  40.         int lim = n*2;
  41.         while (i < lim){
  42.             while (i < m){
  43.                 cout << elements[i] << ' ';
  44.                 i++;
  45.             }
  46.             m *= 2;
  47.             cout << "\n";
  48.         }
  49.     }
  50. };
  51.  
  52. int main(){
  53.     ios_base::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.     int n, m;
  57.     cin >> n >> m;
  58.     tree<ll> T(n);
  59.     while (m-->0){
  60.         char q;
  61.         cin >> q;
  62.         if (q == '+'){
  63.             int a, b, x;
  64.             cin >> a >> b >> x;
  65.             T.add(a-1, b-1, 0, T.n-1, 1, x);
  66.         }
  67.         if (q == '?'){
  68.             int i;
  69.             cin >> i;
  70.             cout << T.read(i-1) << '\n';
  71.         }
  72.     }
  73.     // T.print();
  74.     return 0;
  75. }
  76. /*
  77. 10 5
  78. + 1 5 2
  79. ? 4
  80. + 2 8 99
  81. ? 3
  82. ? 9
  83. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top