fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int oo = 1e18 + 7;
  5. int n, m;
  6. int a[100005];
  7. int st[4 * 100005], lazy[4 * 100005];
  8.  
  9. void down(int id, int l, int r) {
  10.     int t = lazy[id];
  11.     if (t && l != r) {
  12.         lazy[id * 2] += t;
  13.         lazy[id * 2 + 1] += t;
  14.         int mid = (l + r) / 2;
  15.         st[id * 2] += t * (mid - l + 1);
  16.         st[id * 2 + 1] += t * (r - mid);
  17.         lazy[id] = 0;
  18.     }
  19. }
  20.  
  21. void upd(int id, int l, int r, int u, int v, int val) {
  22.     if (r < u || l > v) return;
  23.     if (l >= u && r <= v) {
  24.         st[id] += val * (r - l + 1);
  25.         lazy[id] += val;
  26.         return;
  27.     }
  28.     down(id, l, r);
  29.     int mid = (l + r) / 2;
  30.     upd(id * 2, l, mid, u, v, val);
  31.     upd(id * 2 + 1, mid + 1, r, u, v, val);
  32.     st[id] = st[id * 2] + st[id * 2 + 1];
  33. }
  34.  
  35. int get(int id, int l, int r, int u, int v) {
  36.     if (l > v || r < u) return 0;
  37.     if (l >= u && r <= v) return st[id];
  38.     int mid = (l + r) / 2;
  39.     down(id, l, r);
  40.     return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
  41. }
  42.  
  43. main() {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(0); cout.tie(0);
  46.     freopen("TEST.inp", "r", stdin);
  47.     freopen("TEST.out", "w", stdout);
  48.     cin >> n >> m;
  49.  
  50.     while (m--) {
  51.         int type;
  52.         cin >> type;
  53.  
  54.         if (type == 1) {
  55.             int u, v, x;
  56.             cin >> u >> v >> x;
  57.             u++;
  58.             v++;
  59.             upd(1, 1, n, u, v - 1, x);
  60.  
  61.         } else {
  62.             int l, r;
  63.             cin >> l >> r;
  64.             l++;
  65.             r++;
  66.  
  67.             cout << get(1, 1, n, l, r - 1) << '\n';
  68.  
  69.         }
  70.  
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tvp1VV
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!