Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <iostream>
- # include <stdio.h>
- # include <string>
- # include <vector>
- # include <algorithm>
- # include <string.h>
- using namespace std;
- struct SegmentTree
- {
- int Lpos, Rpos;
- int prod;
- SegmentTree* LTree, *Rtree;
- };
- SegmentTree* build(vector<int> &a, int L, int R)
- {
- if (L == R)
- {
- SegmentTree* tree = new SegmentTree;
- tree->prod = a[L];
- tree->Lpos = tree->Rpos = L;
- tree->LTree = tree->Rtree = NULL;
- return tree;
- }
- int M = (L + R) / 2;
- SegmentTree* LeftTree = build(a, L, M);
- SegmentTree* RightTree = build(a, M+1, R);
- SegmentTree * Tree = new SegmentTree;
- Tree->LTree = LeftTree; Tree->Rtree = RightTree;
- Tree->Lpos = LeftTree->Lpos; Tree->Rpos = RightTree->Rpos;
- Tree->prod = LeftTree->prod * RightTree->prod;
- return Tree;
- }
- void update(SegmentTree* &tree, int val, int pos)
- {
- if (tree->Lpos == tree->Rpos)
- {
- tree->prod = val;
- return;
- }
- if (pos <= tree->LTree->Rpos)
- update(tree->LTree, val, pos);
- else update(tree->Rtree, val, pos);
- tree->prod = tree->LTree->prod * tree->Rtree->prod;
- }
- int multiply(SegmentTree* tree, int L, int R)
- {
- if (L < tree->Lpos)
- L = tree->Lpos;
- if (R > tree->Rpos)
- R = tree->Rpos;
- if (L > R)
- return 1;
- if ((tree->Lpos == L) && (tree->Rpos == R))
- return tree->prod;
- int LeftProd = multiply(tree->LTree, L, R);
- int RightProd = multiply(tree->Rtree, L, R);
- return LeftProd * RightProd;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- int n, k, i, v, j;
- char cmd;
- while (cin >> n >> k)
- {
- vector<int> a(n);
- vector<int> res;
- for (int mi = 0; mi < n; ++mi){
- scanf("%d", &a[mi]);
- if (a[mi] > 0) a[mi] = 1;
- if (a[mi] < 0) a[mi] = -1;
- }
- SegmentTree * Tree = build(a, 0, n - 1);
- for (int ki = 0; ki < k; ki++) {
- cin >> cmd;
- switch (cmd){
- case 'C':
- cin >> i >> v;
- --i;
- if (v > 0) v = 1;
- if (v < 0) v = -1;
- update(Tree, v, i);
- break;
- case 'P' :
- cin >> i >> j;
- --i; --j;
- res.push_back(multiply(Tree,i,j));
- break;
- }
- }
- for (int l = 0; l < res.size(); ++l)
- {
- if (res[l] == 1) printf("+");
- else if (res[l] == -1) printf("-");
- else printf("0");
- }
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement