Advertisement
Guest User

Untitled

a guest
Oct 25th, 2014
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.15 KB | None | 0 0
  1. # include <iostream>
  2. # include <stdio.h>
  3. # include <string>
  4. # include <vector>
  5. # include <algorithm>
  6. # include <string.h>
  7. using namespace std;
  8. struct SegmentTree
  9. {
  10. int Lpos, Rpos;
  11. int prod;
  12. SegmentTree* LTree, *Rtree;
  13. };
  14. SegmentTree* build(vector<int> &a, int L, int R)
  15. {
  16. if (L == R)
  17. {
  18. SegmentTree* tree = new SegmentTree;
  19. tree->prod = a[L];
  20. tree->Lpos = tree->Rpos = L;
  21. tree->LTree = tree->Rtree = NULL;
  22. return tree;
  23. }
  24. int M = (L + R) / 2;
  25. SegmentTree* LeftTree = build(a, L, M);
  26. SegmentTree* RightTree = build(a, M+1, R);
  27. SegmentTree * Tree = new SegmentTree;
  28. Tree->LTree = LeftTree; Tree->Rtree = RightTree;
  29. Tree->Lpos = LeftTree->Lpos; Tree->Rpos = RightTree->Rpos;
  30. Tree->prod = LeftTree->prod * RightTree->prod;
  31. return Tree;
  32. }
  33.  
  34. void update(SegmentTree* &tree, int val, int pos)
  35. {
  36. if (tree->Lpos == tree->Rpos)
  37. {
  38. tree->prod = val;
  39. return;
  40. }
  41. if (pos <= tree->LTree->Rpos)
  42. update(tree->LTree, val, pos);
  43. else update(tree->Rtree, val, pos);
  44. tree->prod = tree->LTree->prod * tree->Rtree->prod;
  45. }
  46.  
  47. int multiply(SegmentTree* tree, int L, int R)
  48. {
  49. if (L < tree->Lpos)
  50. L = tree->Lpos;
  51. if (R > tree->Rpos)
  52. R = tree->Rpos;
  53. if (L > R)
  54. return 1;
  55. if ((tree->Lpos == L) && (tree->Rpos == R))
  56. return tree->prod;
  57. int LeftProd = multiply(tree->LTree, L, R);
  58. int RightProd = multiply(tree->Rtree, L, R);
  59. return LeftProd * RightProd;
  60. }
  61.  
  62. int main()
  63. {
  64. int n, k, i, v, j;
  65. char cmd;
  66. while (cin >> n >> k)
  67. {
  68. vector<int> a(n);
  69. vector<int> res;
  70. for (int mi = 0; mi < n; ++mi){
  71. scanf("%d", &a[mi]);
  72. if (a[mi] > 0) a[mi] = 1;
  73. if (a[mi] < 0) a[mi] = -1;
  74. }
  75. SegmentTree * Tree = build(a, 0, n - 1);
  76. for (int ki = 0; ki < k; ki++) {
  77. cin >> cmd;
  78. switch (cmd){
  79. case 'C':
  80. cin >> i >> v;
  81. if (v > 0) v = 1;
  82. if (v < 0) v = -1;
  83. update(Tree, v, i);
  84. break;
  85. case 'P' :
  86. cin >> i >> j;
  87. res.push_back(multiply(Tree,i,j));
  88. break;
  89. }
  90. }
  91. for (int l = 0; l < res.size(); ++l)
  92. {
  93. if (res[l] == 1) printf("+");
  94. else if (res[l] == -1) printf("-");
  95. else printf("0");
  96. }
  97. printf("\n");
  98. }
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement