Guest User

Untitled

a guest
Nov 21st, 2019
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define asp ""
  4. #define aps ''
  5. #define one 1
  6. #define two 2
  7. #define dif !=
  8. const int maxn = 1e5 + 5;
  9. struct Node{
  10. int menor,igual,maior;
  11. };
  12. vector<Node> tree(4*maxn);
  13.  
  14. void update(int pos,int i,int j,int x,int val){
  15.  
  16. int esq = two*pos;
  17. int dir = two*pos + one;
  18. int mid = (i+j)/two;
  19.  
  20. if(i == j){
  21. if(val == 0){
  22. tree[pos].igual = one;
  23. tree[pos].menor = 0;
  24. tree[pos].maior = 0;
  25. }
  26. else if(val == one){
  27. tree[pos].igual = 0;
  28. tree[pos].menor = 0;
  29. tree[pos].maior = one;
  30. }
  31. else{
  32. tree[pos].igual = 0;
  33. tree[pos].menor = one;
  34. tree[pos].maior = 0;
  35. }
  36. }
  37. else{
  38.  
  39. if(x <= mid) update(esq,i,mid,x,val);
  40. else update(dir,mid+one,j,x,val);
  41.  
  42. tree[pos].igual = tree[esq].igual + tree[dir].igual;
  43. tree[pos].maior = tree[esq].maior + tree[dir].maior;
  44. tree[pos].menor = tree[esq].menor + tree[dir].menor;
  45. }
  46. }
  47.  
  48. Node query(int pos,int i,int j,int l,int r){
  49.  
  50. int esq = two*pos;
  51. int dir = two*pos + one;
  52. int mid = (i+j)/two;
  53. Node aux = {0,0,0};
  54. Node auxa = {0,0,0};
  55.  
  56. if(i > r || j < l) return aux;
  57. else if(i >= l && j <= r) return tree[pos];
  58. else{
  59. aux = query(esq,i,mid,l,r);
  60. auxa = query(dir,mid+one,j,l,r);
  61. aux.igual += auxa.igual;
  62. aux.menor += auxa.menor;
  63. aux.maior += auxa.maior;
  64. }
  65.  
  66. return aux;
  67. }
  68.  
  69. int main(){
  70.  
  71. int n,k;
  72. while(scanf("%d %d",&n,&k) == two){
  73. vector<char> kkk;
  74. for(int i=0;i<n;i++){
  75. int a;
  76. scanf("%d",&a);
  77. if(a < 0) a = -one;
  78. if(a > 0) a = one;
  79. update(one,0,n-one,i,a);
  80. }
  81.  
  82. while(k--){
  83. int l, r;
  84. char op;
  85. scanf(" %c %d %d",&op,&l,&r);
  86. if(op == 'C'){
  87. l--;
  88. if(r > 0) r = one;
  89. if(r < 0) r = -one;
  90. update(one,0,n-one,l,r);
  91. continue;
  92. }
  93. l--;
  94. r--;
  95. Node ans = query(one,0,n-one,l,r);
  96. if(ans.igual > 0) kkk.push_back('0');
  97. else if(ans.menor%two == 0) kkk.push_back('+');
  98. else kkk.push_back('-');
  99. }
  100. for(int i=0;i<kkk.size();i++){
  101. printf("%c",kkk[i]);
  102. }
  103. printf("\n");
  104. }
  105. }
RAW Paste Data