Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int get_sign(int broj)
  7. {
  8. if(broj < 0)
  9. return(-1);
  10. if(broj > 0)
  11. return(1);
  12.  
  13. return(0);
  14.  
  15. }
  16.  
  17. class SegmentTree
  18. {
  19. private:
  20. vector<int> st, niza; // st = segment tree
  21. int n;
  22. int left (int p) { return p << 1; } // same as binary heap operations, i.e. p*2 and p*2 + 1
  23. int right(int p) { return (p << 1) + 1; }
  24.  
  25. void build(int p, int L, int R) // O(n log n)
  26. {
  27. if (L == R)
  28. {
  29. st[p] = niza[L];
  30. return;
  31. }
  32.  
  33. build(left(p), L, (L + R) / 2);
  34. build(right(p), (L + R) / 2 + 1, R);
  35.  
  36. int p1 = st[left(p)], p2 = st[right(p)];
  37. st[p] = p1 * p2;
  38. }
  39.  
  40. //TODO: test
  41. int rmq(int p, int L, int R, int i, int j)
  42. {
  43. if (i > R || j < L) return 1; // current segment outside query range
  44.  
  45. if (L >= i && R <= j)
  46. {
  47. //cout << st[p] << " " << p << endl;
  48. return st[p];
  49. }
  50.  
  51. // compute the min position in the left and right part of the interval
  52. int p1 = rmq(left(p) , L, (L+R) / 2, i, j);
  53. int p2 = rmq(right(p), (L+R) / 2 + 1, R, i, j);
  54.  
  55. //cout << p1 << " " << p2 << endl;
  56.  
  57. return (p1*p2);
  58. }
  59.  
  60. void update_element(int p, int L, int R, int idx1, int val) // O(log n)
  61. {
  62. if(L == R)
  63. {
  64. //cout << L << " " << p << " " << idx1 << endl;
  65. if(L == idx1)
  66. change_value(p, idx1, val);
  67. return;
  68. }
  69.  
  70. if (idx1 > R || idx1 < L)
  71. return;
  72.  
  73. update_element(left(p), L, (L+R) / 2, idx1, val);
  74. update_element(right(p), (L+R) / 2 + 1, R, idx1, val);
  75.  
  76. st[p] = st[left(p)] * st[right(p)];
  77.  
  78. return;
  79. }
  80.  
  81.  
  82. void change_value(int p, int idx, int val)
  83. {
  84. niza[idx] = val;
  85. st[p] = val;
  86. return;
  87. }
  88.  
  89.  
  90. public:
  91. SegmentTree(const vector<int> &_niza)
  92. {
  93. niza = _niza; n = (int)niza.size();
  94. st.assign(4 * n, 0);
  95. build(1, 0, n - 1);
  96. }
  97.  
  98. void update(int idx1, int val)
  99. {
  100. update_element(1, 0, n-1, idx1, val);
  101. }
  102.  
  103. void pecati()
  104. {
  105. for(int i = 0; i < niza.size(); i++)
  106. cout << niza[i] << " ";
  107. cout << endl;
  108. }
  109. void pecati_st()
  110. {
  111.  
  112. for(int i = 0; i < st.size(); i++)
  113. cout << st[i] << " ";
  114.  
  115. cout << endl;
  116. }
  117.  
  118. int rmq(int i, int j)
  119. {
  120. if(i < 0 || j >= niza.size())
  121. {
  122. cout << "Invalid segment range!" << endl;
  123. return(-1);
  124. }
  125. return rmq(1, 0, n - 1, i, j);
  126. }
  127.  
  128. };
  129.  
  130.  
  131. int main()
  132. {
  133. int n, q;
  134. int broj;
  135.  
  136. while(cin >> n >> q)
  137. {
  138. vector<int> broevi(n);
  139. for(int i = 0; i < n; i++)
  140. {
  141. cin >> broj;
  142. broevi[i] = get_sign(broj);
  143. }
  144.  
  145. SegmentTree st(broevi);
  146.  
  147. int t1, t2;
  148. char op;
  149. string rez = "";
  150.  
  151. for(int i = 0; i < q; i++)
  152. {
  153. cin >> op;
  154. cin >> t1 >> t2;
  155.  
  156. if(op == 'C')
  157. {
  158. t1--;
  159. t2 = get_sign(t2);
  160. st.update(t1, t2);
  161. }
  162. else if(op == 'P')
  163. {
  164. t1--;
  165. t2--;
  166. int t_rez = st.rmq(t1, t2);
  167.  
  168. if(t_rez < 0)
  169. rez += '-';
  170. else if(t_rez > 0)
  171. rez += '+';
  172. else
  173. rez += '0';
  174. }
  175. }
  176. cout << rez << endl;
  177. }
  178. return(0);
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement