Advertisement
Arrias

Untitled

Dec 12th, 2018
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define mp make_pair
  7.  
  8. ll const N = 100005;
  9.  
  10. struct Tree
  11. {
  12. ll add = -1, sum = 0, tl, tr;
  13. } t[4 * N];
  14.  
  15. void push(ll i)
  16. {
  17. if (t[i].add != -1) {
  18. if (t[i].tl + 1 == t[i].tr) {
  19. t[i].sum = t[i].add;
  20. }
  21. else {
  22. t[i].sum = (t[i].tr - t[i].tl) * t[i].add;
  23. t[i * 2].add = t[i].add;
  24. t[i * 2 + 1].add = t[i].add;
  25. }
  26. }
  27. t[i].add = -1;
  28. }
  29.  
  30. void build(ll i, ll l, ll r)
  31. {
  32. t[i].tl = l, t[i].tr = r;
  33. if (l + 1 == r) {
  34. return;
  35. }
  36. build(i * 2, l, (l + r) / 2);
  37. build(i * 2 + 1, (l + r) / 2, r);
  38. }
  39.  
  40. void update(ll i, ll l, ll r, ll x)
  41. {
  42. push(i);
  43. if (l <= t[i].tl && t[i].tr <= r) {
  44. t[i].add = x;
  45. push(i);
  46. return;
  47. }
  48. else if (t[i].tr <= l || t[i].tl >= r) {
  49. return;
  50. }
  51. update(i * 2, l, r, x);
  52. update(i * 2 + 1, l, r, x);
  53. t[i].sum = t[i * 2].sum + t[i * 2 + 1].sum;
  54. }
  55.  
  56. ll get(ll i, ll l, ll r)
  57. {
  58. push(i);
  59. if (l <= t[i].tl && t[i].tr <= r) {
  60. return t[i].sum;
  61. }
  62. else if (t[i].tr <= l || t[i].tl >= r) {
  63. return 0;
  64. }
  65. return get(i * 2, l, r) + get(i * 2 + 1, l, r);
  66. }
  67.  
  68. int main()
  69. {
  70. freopen("sum.in", "r", stdin);
  71. freopen("sum.out", "w", stdout);
  72. ll n, k;
  73. cin >> n >> k;
  74. build(1, 0, n);
  75. while (k--) {
  76. char tt;
  77. cin >> tt;
  78. if (tt == 'A') {
  79. ll l, r, z;
  80. cin >> l >> r >> z;
  81. update(1, l - 1, r, z);
  82. }
  83. else {
  84. ll l, r;
  85. cin >> l >> r;
  86. cout << get(1, l - 1, r) << '\n';
  87. }
  88. }
  89. return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement