Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.51 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. #define gc getchar_unlocked
  3.  
  4. using namespace std;
  5.  
  6. inline void wpisz(int &x)
  7. {
  8. x = 0;
  9. long long mnoz = 1;
  10. register char c = gc();
  11. if(c == '-')
  12. {
  13. mnoz = -1;
  14. c = gc();
  15. }
  16. for(;c<48||c>57;c=gc());
  17. for(;c>47&&c<58;c=gc())
  18. x = ((x<<3) + (x<<1) + c-48);
  19. x *= mnoz;
  20. }
  21.  
  22. /*void update(int* tree, int leaf_index, int value, bool node = false) {
  23. if (leaf_index < 1) return;
  24. if(node)
  25. {
  26. tree[leaf_index] = tree[leaf_index * 2] + tree[leaf_index * 2 + 1];
  27. }
  28. else
  29. {
  30. tree[leaf_index] = value;
  31. }
  32. update(tree, leaf_index/2, value, true);
  33. }*/
  34.  
  35. void update(int* tree, int leaf_index, int value)
  36. {
  37. if(tree[leaf_index] != value)
  38. {
  39. tree[leaf_index] = value;
  40. if(value == 0) value = -1;
  41. leaf_index /= 2;
  42. while(leaf_index > 0)
  43. {
  44. tree[leaf_index] += value;
  45. leaf_index /= 2;
  46. }
  47. }
  48. }
  49.  
  50.  
  51. int query(int v, int L, int R , int a, int b, int* tree) //'v' jest numerem węzła w drzewie
  52. {
  53. if (L == a && R == b) {
  54. return tree[v];
  55. }
  56.  
  57. int mid = (a + b) / 2;
  58. if (R <= mid) {
  59. return query(2 * v, L, R, a, mid, tree);
  60. } else if (L > mid) {
  61. return query(2 * v + 1, L, R, mid + 1, b, tree);
  62. } else {
  63. return query(2 * v, L, mid, a, mid, tree) + query(2 * v + 1, mid + 1, R, mid + 1, b, tree);
  64. }
  65. }
  66.  
  67. int main()
  68. {
  69. std::ios_base::sync_with_stdio(0);
  70. int q, k, x, v, L, R, n, value, operation;
  71. wpisz(n);
  72. wpisz(q);
  73. wpisz(k);
  74. const int LEAF_COUNT = pow(2,ceil(log2(n))); // ile lisci
  75. const int TREE_SIZE = 2 * LEAF_COUNT; // ile nodeow w drzewie
  76. int* tree = new int[TREE_SIZE]; // robimy drzewo
  77. for(int i = 0; i < TREE_SIZE; i++)
  78. {
  79. tree[i] = 0;
  80. }
  81. for(int i = 0; i < n; i++) // tutaj wbijamy nasze pierwsze liczby
  82. {
  83. wpisz(x); // tu x uzywamy do wartosci
  84. if(x <= k) value = 0;
  85. else value = 1;
  86. update(tree, i + LEAF_COUNT, value);
  87. }
  88.  
  89. for(int i = 0; i < q; i++) // operacje
  90. {
  91. wpisz(operation);
  92. if(operation == 0)
  93. {
  94. wpisz(x);
  95. wpisz(v);
  96. v = v <= k ? 0 : 1;
  97. x += (LEAF_COUNT-1);
  98. update(tree, x, v);
  99. }
  100. else
  101. {
  102. wpisz(L);
  103. wpisz(R);
  104. cout << query(1, L, R, 1, LEAF_COUNT, tree) << "\n";
  105. }
  106. }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement