SHARE
TWEET

Untitled

a guest Jan 19th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. #define fi first
  9. #define se second
  10.  
  11. const int N = 1e5 + 10;
  12.  
  13. ll sum[4 * N];
  14. ll add[4 * N];
  15.  
  16. void push(int v, int l, int r) {
  17.     int m = (l + r) / 2;
  18.     add[v * 2 + 1] += add[v];
  19.     sum[v * 2 + 1] += (m - l + 1) * add[v];
  20.     add[v * 2 + 2] += add[v];
  21.     sum[v * 2 + 2] += (r - (m + 1) + 1) * add[v];
  22.     add[v] = 0;
  23. }
  24.  
  25. void upd(int l, int r, int tl, int tr, int v, int x) {
  26.     if (l > tr || r < tl) {
  27.         return;
  28.     }
  29.     if (l <= tl && r >= tr) {
  30.         sum[v] += (tr - tl + 1) * x;
  31.         add[v] += x;
  32.     } else {
  33.         push(v, tl, tr);
  34.         int tm = (tl + tr) >> 1;
  35.         upd(l, r, tl, tm, v * 2 + 1, x);
  36.         upd(l, r, tm + 1, tr, v * 2 + 2, x);
  37.         sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
  38.     }
  39. }
  40.  
  41. ll get(int l, int r, int tl, int tr, int v) {
  42.     if (l > tr || r < tl) {
  43.         return 0;
  44.     }
  45.     if (l <= tl && r >= tr) {
  46.         return sum[v];
  47.     } else {
  48.         push(v, tl, tr);
  49.         int tm = (tl + tr) >> 1;
  50.         return get(l, r, tl, tm, v * 2 + 1) + get(l, r, tm + 1, tr, v * 2 + 2);
  51.     }
  52. }
  53.  
  54. int main() {
  55. #ifdef LOCAL
  56.     freopen("input.txt", "rt", stdin);
  57.     freopen("output.txt", "wt", stdout);
  58. #endif
  59.     ios_base::sync_with_stdio(0);
  60.     cin.tie(0);
  61.     int n;
  62.     cin >> n;
  63.     for (int i = 0; i < n; ++i) {
  64.         int a;
  65.         cin >> a;
  66.         upd(i, i, 0, n - 1, 0, a);
  67.     }
  68.     int q;
  69.     cin >> q;
  70.     while (q--) {
  71.         int t;
  72.         cin >> t;
  73.         if (t == 1) {
  74.             int l, r;
  75.             cin >> l >> r;
  76.             l--;
  77.             r--;
  78.             cout << get(l, r, 0, n - 1, 0) << '\n';
  79.         } else {
  80.             int l, r;
  81.             ll x;
  82.             cin >> l >> r >> x;
  83.             l--;
  84.             r--;
  85.             upd(l, r, 0, n - 1, 0, x);
  86.         }
  87.     }
  88.     return 0;
  89. }
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