Advertisement
Guest User

Untitled

a guest
Jan 19th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement