Advertisement
konchin_shih

Untitled

Sep 26th, 2020
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<functional>
  5. #define endl '\n'
  6. using namespace std;
  7. int main() {
  8. cin.tie(nullptr);
  9. ios::sync_with_stdio(false);
  10. int n, q, op, a, b, k;
  11. cin >> n >> q;
  12. vector<long long> seg(n << 2, 0LL), d(n << 2, 0LL);
  13. auto lch = [](int x) {return x << 1 ;};
  14. auto rch = [](int x) {return x << 1 | 1;};
  15. auto push = [&](int i, int l, int r) {
  16. if (!d[i]) return;
  17. seg[i] += d[i] * (r - l + 1);
  18. d[lch(i)] += d[i], d[rch(i)] += d[i];
  19. d[i] = 0;
  20. };
  21. auto rmodify = [&](int ql, int qr, long long x) {
  22. function<void(int, int, int)> _ = [&](int i, int l, int r) {
  23. push(i, l, r);
  24. if (qr < l || r < ql) return;
  25. if (ql <= l && r <= qr) {
  26. d[i] += x, push(i, l, r);
  27. return;
  28. }
  29. int m = (l + r) >> 1;
  30. _(lch(i), l, m), _(rch(i), m + 1, r);
  31. seg[i] = seg[lch(i)] + seg[rch(i)];
  32. }; _(1, 1, n);
  33. };
  34. auto query = [&](int ql, int qr) {
  35. function<long long(int, int, int)> _ = [&](int i, int l, int r) {
  36. push(i, l, r);
  37. if (qr < l || r < ql) return 0LL;
  38. if (ql <= l && r <= qr) return seg[i];
  39. int m = (l + r) >> 1;
  40. return _(lch(i), l, m) + _(rch(i), m + 1, r);
  41. }; return _(1, 1, n);
  42. };
  43. for (int i = 1; i <= n; i++)
  44. cin >> k, rmodify(i, i, k);
  45. while (q-- && cin >> op)
  46. switch (op) {
  47. case 0:
  48. cin >> a >> b >> k;
  49. rmodify(a, b, k);
  50. break;
  51. case 1:
  52. cin >> a >> b;
  53. cout << query(a, b) << endl;
  54. break;
  55. }
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement