Guest User

Untitled

a guest
Aug 15th, 2015
320
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.32 KB | None | 0 0
  1. #include <cstring>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <memory.h>
  21. #include <cassert>
  22.  
  23. typedef long long ll;
  24.  
  25. using namespace std;
  26.  
  27. const int MAX_N = 10000;
  28.  
  29. ll value[40000];
  30. ll delta[40000];
  31. ll default_delta = -1; // should be impossilbe value;
  32.  
  33. void build_tree(int a[], int root, int tl, int tr){
  34. if(tl == tr){
  35. value[root] = a[tl];
  36. }else{
  37. int mid = (tl+tr)>>1;
  38. build_tree(a, root*2+1, tl, mid);
  39. build_tree(a, root*2+2, mid+1, tr);
  40. value[root] = value[root*2+1]+value[root*2+2];
  41. delta[root] = default_delta;
  42. }
  43. }
  44. ll acc(ll value, ll deltas, ll length) {
  45. if(deltas != default_delta)
  46. return value + deltas * length;
  47. return value;
  48. }
  49. ll joinDelta(ll was, ll deltas) {
  50. if(deltas != default_delta) //
  51. return deltas;
  52. return was;
  53. }
  54. ll joinValue(ll left, ll right) {
  55. return left + right;
  56. }
  57. void pushDown(int root, int left, int middle, int right) {
  58. value[2 * root + 1] = acc(value[2 * root + 1], delta[root], middle - left + 1);
  59. value[2 * root + 2] = acc(value[2 * root + 2], delta[root], right - middle);
  60. delta[2 * root + 1] = joinDelta(delta[2 * root + 1], delta[root]);
  61. delta[2 * root + 2] = joinDelta(delta[2 * root + 2], delta[root]);
  62. delta[root] = default_delta;
  63. }
  64. void updateFull(int root, int left, int right, int from, int to, ll deltas) {
  65. value[root] = acc(value[root], deltas, right - left + 1);
  66. delta[root] = joinDelta(delta[root], deltas);
  67. }
  68. void updatePreProcess(int root, int left, int right, int from, int to, ll deltas, int middle) {
  69. pushDown(root, left, middle, right);
  70. }
  71. void updatePostProcess(int root, int left, int right, int from, int to, ll deltas, int middle) {
  72. value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
  73. }
  74.  
  75.  
  76. void update(int root, int left, int right, int from, int to, ll deltas) {
  77. if (left > to || right < from)
  78. return;
  79. if (left >= from && right <= to) {
  80. updateFull(root, left, right, from, to, deltas);
  81. return;
  82. }
  83. int middle = (left + right) >> 1;
  84. updatePreProcess(root, left, right, from, to, deltas, middle);
  85. update(2 * root + 1, left, middle, from, to, deltas);
  86. update(2 * root + 2, middle + 1, right, from, to, deltas);
  87. updatePostProcess(root, left, right, from, to, deltas, middle);
  88. }
  89.  
  90. void queryPreProcess(int root, int left, int right, int from, int to, int middle) {
  91. pushDown(root, left, middle, right);
  92. }
  93. ll queryPostProcess(int root, int left, int right, int from, int to, int middle, ll leftResult, ll rightResult) {
  94. return joinValue(leftResult, rightResult);
  95. }
  96. ll queryFull(int root, int left, int right, int from, int to) {
  97. return value[root];
  98. }
  99. ll query(int root, int left, int right, int from, int to) {
  100. if (left > to || right < from)
  101. return 0;
  102. if (left >= from && right <= to)
  103. return queryFull(root, left, right, from, to);
  104. int middle = (left + right) >> 1;
  105. queryPreProcess(root, left, right, from, to, middle);
  106. ll leftResult = query(2 * root + 1, left, middle, from, to);
  107. ll rightResult = query(2 * root + 2, middle + 1, right, from, to);
  108. return queryPostProcess(root, left, right, from, to, middle, leftResult, rightResult);
  109. }
  110.  
  111. int main(){
  112. int n;
  113. scanf("%d", &n);
  114. int a[n];
  115. for(int i = 0; i < n; i++) a[i] = 0;
  116. build_tree(a, 1, 0, n-1);
  117. int m;
  118. scanf("%d", &m);
  119. for(int i = 0; i < m; i++){
  120. int type;
  121. scanf("%d", &type); // 1 - sum [l, r], 2 - update [l, r] = x;
  122. if(type == 1){
  123. int l, r;
  124. scanf("%d %d", &l, &r);
  125. printf("%d \n", query(1, 0, n-1, l-1, r-1));
  126. }
  127. else{
  128. int l, r;
  129. ll x;
  130. scanf("%d %d %lld", &l, &r, &x);
  131. update(1, 0, n-1, l-1, r-1, x);
  132. }
  133. }
  134. return 0;
  135. }
Advertisement
Add Comment
Please, Sign In to add comment