Advertisement
Guest User

Untitled

a guest
Oct 25th, 2014
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.02 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. ios_base::sync_with_stdio(false);
  65.       int n, k, i, v, j;
  66.       char cmd;
  67.       while (cin >> n >> k)
  68.       {
  69.               vector<int> a(n);
  70.               vector<int> res;
  71.               for (int mi = 0; mi < n; ++mi){
  72.                       scanf("%d", &a[mi]);
  73.                       if (a[mi] > 0)  a[mi] = 1;
  74.                   if (a[mi] < 0)  a[mi] = -1;
  75.               }
  76.               SegmentTree * Tree = build(a, 0, n - 1);
  77.               for (int ki = 0; ki < k; ki++) {
  78.                       cin >> cmd;
  79.                       switch (cmd){
  80.                       case 'C':
  81.                               cin >> i >> v;
  82. --i;
  83.                               if (v > 0) v = 1;
  84.                               if (v < 0) v = -1;
  85.                               update(Tree, v, i);
  86.                               break;
  87.                       case 'P' :
  88.                               cin >> i >> j;
  89. --i; --j;
  90.                               res.push_back(multiply(Tree,i,j));
  91.                               break;
  92.                       }
  93.               }
  94.               for (int l = 0; l < res.size(); ++l)
  95.               {
  96.                       if (res[l] == 1) printf("+");
  97.                       else if (res[l] == -1) printf("-");
  98.                       else  printf("0");
  99.               }
  100.               printf("\n");
  101.       }
  102.       return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement