Guest User

Untitled

a guest
Sep 27th, 2021
302
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.66 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int maxN = 1e5;
  6.  
  7. int n;
  8.  
  9. struct SegmentTree {
  10. vector<long long> t = vector<long long> (maxN * 4);
  11. vector<long long> lazy = vector<long long> (maxN * 4);
  12. //made changes to the push function
  13. void push(int x,int l1,int r1,int l2,int r2){
  14. lazy[2 * x] += lazy[x];
  15. lazy[2 * x + 1] += lazy[x];
  16. t[2*x]+=lazy[x]*(r1-l1+1);
  17. t[2*x+1]+=lazy[x]*(r2-l2+1);
  18. lazy[x] = 0;
  19. }
  20. void upd(int x, int lx, int rx, int l, int r, long long val) {
  21. if(lx >= l && rx <= r) {
  22. lazy[x]+=val;
  23. t[x]+=val*(rx-lx+1);
  24. return;
  25. }
  26. if(lx > r || rx < l) {return;}
  27. int m = (lx + rx) / 2;
  28. push(x,lx,m,m+1,rx);
  29. upd(2 * x, lx, m, l, r, val);
  30. upd(2 * x + 1, m + 1, rx, l, r, val);
  31. t[x]=t[2*x]+t[2*x+1];//also added this
  32. }
  33. void upd(int l, int r, long long val) {
  34. upd(1, 0, n - 1, l, r, val);
  35. }
  36. long long query(int x, int lx, int rx, int l, int r) {
  37. if(lx >= l && rx <= r) {
  38. return t[x];
  39. }
  40. if(lx > r || rx < l) {return 0;}
  41. int m = (lx + rx) / 2;
  42. push(x,lx,m,m+1,rx);
  43. return query(2 * x, lx, m, l, r) + query(2 * x + 1, m + 1, rx, l, r);
  44. }
  45. long long query(int l, int r) {
  46. return query(1, 0, n - 1, l, r);
  47. }
  48. };
  49.  
  50. int main() {
  51. ios::sync_with_stdio(false);
  52. cin.tie(0);
  53. int m;
  54. cin >> n >> m;
  55. SegmentTree st;
  56. for (int i = 0; i<m; i++) {
  57. int type;
  58. cin >> type;
  59. if(type == 1) {
  60. long long l,r,v;
  61. cin >> l >> r >> v;
  62. r--;
  63. st.upd(l, r, v);
  64. continue;
  65. }
  66. int l, r;
  67. cin >> l >> r;
  68. r--;
  69. cout << st.query(l, r) << '\n';
  70. }
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment