Advertisement
konchin_shih

Untitled

Sep 26th, 2020
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 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. seg[i] += d[i] * (r - l + 1);
  17. d[lch(i)] += d[i], d[rch(i)] += d[i];
  18. d[i] = 0;
  19. };
  20. auto rmodify = [&](int ql, int qr, long long x) {
  21. function<void(int, int, int)> _ = [&](int id, int l, int r) {
  22. push(id, l, r);
  23. if (qr < l || r < ql) return;
  24. if (ql <= l && r <= qr) {
  25. seg[id] += x, d[id] += x;
  26. return;
  27. }
  28. int m = (l + r) >> 1;
  29. _(lch(id), l, m), _(rch(id), m + 1, r);
  30. seg[id] = seg[lch(id)] + seg[rch(id)];
  31. }; _(1, 0, n - 1);
  32. };
  33. auto query = [&](int ql, int qr) {
  34. function<long long(int, int, int)> _ = [&](int id, int l, int r) {
  35. push(id, l, r);
  36. if (qr < l || r < ql) return 0LL;
  37. if (ql <= l && r <= qr) return seg[id];
  38. int m = (l + r) >> 1;
  39. return _(lch(id), l, m) + _(rch(id), m + 1, r);
  40. }; return _(1, 0, n - 1);
  41. };
  42. for (int i = 0; i != n; i++)
  43. cin >> k, rmodify(i, i, k);
  44. for (const auto& i : seg)
  45. cerr << i << ' ';
  46. cerr << endl;
  47. for (const auto& i : d)
  48. cerr << i << ' ';
  49. cerr << endl;
  50. while (q-- && cin >> op)
  51. switch (op) {
  52. case 0:
  53. cin >> a >> b >> k;
  54. rmodify(a - 1, b - 1, k);
  55. break;
  56. case 1:
  57. cin >> a >> b;
  58. cout << query(a - 1, b - 1) << endl;
  59. break;
  60. }
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement