Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define F first
  4. #define S second
  5. #define all(x) (x).begin(), (x).end()
  6. #define fast cin.tie(0);cin.sync_with_stdio(0);cout.tie(0);cout.sync_with_stdio(0)
  7. #define file freopen("lca_rmq.in", "r", stdin); freopen("lca_rmq.out", "w", stdout)
  8.  
  9. typedef long long ll;
  10. typedef long double ld;
  11. using namespace std;
  12.  
  13. struct nd {
  14. int vl, ad;
  15. };
  16. nd t[888888];
  17. int a[222222];
  18. void push(int v, int l, int r) {
  19. t[v].vl += t[v].ad * max(0, r - l + 1);
  20. t[v * 2].ad += t[v].ad;
  21. t[v * 2 + 1].ad += t[v].ad;
  22. t[v].ad = 0;
  23. }
  24. void upd(int v, int tl, int tr, int l, int r, ll add) {
  25. push(v, tl, tr);
  26. if (l > r) return;
  27. if (tl == l && tr == r) {
  28. t[v].ad += add;
  29. push(v, tl, tr);
  30. }
  31. else {
  32. push(v, tl, tr);
  33. int tm = (tl + tr) / 2;
  34. upd(v * 2, tl, tm, l, min(r, tm), add);
  35. upd(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, add);
  36. t[v].vl = t[v * 2].vl + t[v * 2 + 1].vl;
  37. }
  38. }
  39. ll get_sum(int v, int tl, int tr, int l, int r) {
  40. if (l > r) return 0;
  41. push(v, tl, tr);
  42. if (tl == l && tr == r) return t[v].vl;
  43. int tm = (tl + tr) / 2;
  44. return get_sum(v * 2, tl, tm, l, min(r, tm)) +
  45. get_sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  46. }
  47. signed main() {
  48. fast;
  49. int n, m;
  50. cin >> n >> m;
  51. while (m--) {
  52. int uu;
  53. cin >> uu;
  54. if (uu == 1) {
  55. int l, r, s;
  56. cin >> l >> r >> s;
  57. upd(1, 0, n - 1, l, r - 1, s);
  58. }
  59. else {
  60. int l, r;
  61. cin >> l >> r;
  62. cout << get_sum(1, 0, n - 1, l, r - 1) << endl;
  63. }
  64. }
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement