Advertisement
Guest User

Untitled

a guest
Jun 25th, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.90 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define amen ;
  6.  
  7. typedef long long ll;
  8. typedef double d;
  9. typedef long double lld;
  10. typedef string str;
  11.  
  12. const ll neutral = 1e8;
  13.  
  14. struct node
  15. {
  16. ll left, right, add = neutral, value;
  17. node * left_children, * right_children;
  18. };
  19.  
  20. node* build(ll left, ll right)
  21. {
  22. if (left > right)
  23. return nullptr;
  24. node * res = new node;
  25. res->left = left;
  26. res->right = right;
  27. res->add = neutral;
  28. res->value = 0;
  29. if (left == right)
  30. {
  31. res->left_children = nullptr;
  32. res->right_children = nullptr;
  33. }
  34. else
  35. {
  36. ll m = (left + right) / 2;
  37. res->left_children = build(left, m);
  38. res->right_children = build(m+1, right);
  39. }
  40. return res;
  41. }
  42.  
  43. void push(node * root)
  44. {
  45. if (root->add == neutral)
  46. return;
  47. root->value = root->add * (root->right - root->left + 1);
  48. if (root->left == root->right)
  49. {
  50. root->add = neutral;
  51. return;
  52. }
  53. root->left_children->add = root->add;
  54. root->right_children->add = root->add;
  55. root->add = neutral;
  56. return;
  57. }
  58.  
  59. void update_line(node * root, ll left, ll right, ll add)
  60. {
  61. if (left > root->right || right < root->left)
  62. return;
  63. if (left<= root->left && root->right <= right)
  64. {
  65. root->add = add;
  66. return;
  67. }
  68. push(root);
  69. update_line(root->left_children, left, right, add);
  70. update_line(root->right_children, left, right, add);
  71. push(root->left_children);
  72. push(root->right_children);
  73. root->value = root->left_children->value + root->right_children->value;
  74. }
  75.  
  76. ll sum(node * root, ll left, ll right)
  77. {
  78. if (left > root->right || right < root->left)
  79. return 0;
  80. if (left<= root->left && root->right <= right)
  81. {
  82. push(root);
  83. return root->value;
  84. }
  85. push(root);
  86. return sum(root->left_children, left, right) + sum(root->right_children, left, right);
  87. }
  88.  
  89. void cout_tree(node * root)
  90. {
  91. cout << root->left << " " << root->right << " add: " << root->add << " value : " << root->value << endl;
  92. if (root->left == root->right)
  93. {
  94. return;
  95. }
  96. cout_tree(root->left_children);
  97. cout_tree(root->right_children);
  98. }
  99.  
  100. int main()
  101. {
  102. freopen("sum.in", "r", stdin);
  103. freopen("sum.out", "w", stdout);
  104. ll n, k;
  105. cin >> n >> k;
  106. node * root = build(1, n);
  107. vector <ll> ans;
  108. for (ll i = 0; i < k; i++)
  109. {
  110. char c;
  111. cin >> c;
  112. if (c == 'A')
  113. {
  114. ll l, r, x;
  115. cin >> l >> r >> x;
  116. update_line(root, l, r, x);
  117. }
  118. else
  119. {
  120. ll l, r;
  121. cin >> l >> r;
  122. ans.push_back(sum(root, l, r));
  123. }
  124. //cout_tree(root);
  125. }
  126. for (auto it:ans)
  127. cout << it << endl;
  128.  
  129. return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement