Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int get_sign(int broj)
- {
- if(broj < 0)
- return(-1);
- if(broj > 0)
- return(1);
- return(0);
- }
- class SegmentTree
- {
- private:
- vector<int> st, niza; // st = segment tree
- int n;
- int left (int p) { return p << 1; } // same as binary heap operations, i.e. p*2 and p*2 + 1
- int right(int p) { return (p << 1) + 1; }
- void build(int p, int L, int R) // O(n log n)
- {
- if (L == R)
- {
- st[p] = niza[L];
- return;
- }
- build(left(p), L, (L + R) / 2);
- build(right(p), (L + R) / 2 + 1, R);
- int p1 = st[left(p)], p2 = st[right(p)];
- st[p] = p1 * p2;
- }
- //TODO: test
- int rmq(int p, int L, int R, int i, int j)
- {
- if (i > R || j < L) return 1; // current segment outside query range
- if (L >= i && R <= j)
- {
- //cout << st[p] << " " << p << endl;
- return st[p];
- }
- // compute the min position in the left and right part of the interval
- int p1 = rmq(left(p) , L, (L+R) / 2, i, j);
- int p2 = rmq(right(p), (L+R) / 2 + 1, R, i, j);
- //cout << p1 << " " << p2 << endl;
- return (p1*p2);
- }
- void update_element(int p, int L, int R, int idx1, int val) // O(log n)
- {
- if(L == R)
- {
- //cout << L << " " << p << " " << idx1 << endl;
- if(L == idx1)
- change_value(p, idx1, val);
- return;
- }
- if (idx1 > R || idx1 < L)
- return;
- update_element(left(p), L, (L+R) / 2, idx1, val);
- update_element(right(p), (L+R) / 2 + 1, R, idx1, val);
- st[p] = st[left(p)] * st[right(p)];
- return;
- }
- void change_value(int p, int idx, int val)
- {
- niza[idx] = val;
- st[p] = val;
- return;
- }
- public:
- SegmentTree(const vector<int> &_niza)
- {
- niza = _niza; n = (int)niza.size();
- st.assign(4 * n, 0);
- build(1, 0, n - 1);
- }
- void update(int idx1, int val)
- {
- update_element(1, 0, n-1, idx1, val);
- }
- void pecati()
- {
- for(int i = 0; i < niza.size(); i++)
- cout << niza[i] << " ";
- cout << endl;
- }
- void pecati_st()
- {
- for(int i = 0; i < st.size(); i++)
- cout << st[i] << " ";
- cout << endl;
- }
- int rmq(int i, int j)
- {
- if(i < 0 || j >= niza.size())
- {
- cout << "Invalid segment range!" << endl;
- return(-1);
- }
- return rmq(1, 0, n - 1, i, j);
- }
- };
- int main()
- {
- int n, q;
- int broj;
- while(cin >> n >> q)
- {
- vector<int> broevi(n);
- for(int i = 0; i < n; i++)
- {
- cin >> broj;
- broevi[i] = get_sign(broj);
- }
- SegmentTree st(broevi);
- int t1, t2;
- char op;
- string rez = "";
- for(int i = 0; i < q; i++)
- {
- cin >> op;
- cin >> t1 >> t2;
- if(op == 'C')
- {
- t1--;
- t2 = get_sign(t2);
- st.update(t1, t2);
- }
- else if(op == 'P')
- {
- t1--;
- t2--;
- int t_rez = st.rmq(t1, t2);
- if(t_rez < 0)
- rez += '-';
- else if(t_rez > 0)
- rez += '+';
- else
- rez += '0';
- }
- }
- cout << rez << endl;
- }
- return(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement