Advertisement
Guest User

Untitled

a guest
Jan 19th, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.30 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int maxn = 50005;
  5. int st[maxn << 2], lz[maxn << 2];
  6. void update(int id, int l, int r, int u, int v, int val) {
  7. if (v < l || r < u) return;
  8. if (u <= l && r <= v) {
  9. lz[id] += val;
  10. return;
  11. }
  12. int mid = (l + r) >> 1;
  13. update(id << 1, l, mid, u, v, val);
  14. update(id << 1 | 1, mid + 1, r, u, v, val);
  15. st[id] = max(st[id << 1] + lz[id << 1], st[id << 1 | 1] + lz[id << 1 | 1]);
  16. }
  17. int get(int id, int l, int r, int u, int v) {
  18. if (v < l || r < u) return -1e9;
  19. if (u <= l && r <= v)
  20. return st[id] + lz[id];
  21. int mid = (l + r) >> 1;
  22. return max(get(id << 1, l, mid, u, v),
  23. get(id << 1 | 1, mid + 1, r, u, v)) + lz[id];
  24. }
  25. int main() {
  26. #ifdef LDT
  27. freopen("input.txt", "r", stdin);
  28. //freopen("output.txt", "w", stdout);
  29. #endif
  30. ios_base::sync_with_stdio(false);
  31. cin.tie(NULL);
  32. int n, m;
  33. cin >> n >> m;
  34. for (int i = 1; i <= m; ++i) {
  35. int typ;
  36. cin >> typ;
  37. if (typ == 0) {
  38. int x, y, val;
  39. cin >> x >> y >> val;
  40. update(1, 1, n, x, y, val);
  41. }
  42. else {
  43. int x, y;
  44. cin >> x >> y;
  45. cout << get(1, 1, n, x, y) << '\n';
  46. }
  47. }
  48. return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement