UVa 12532 Interval Product

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

#define sz 100007
int a[sz], tr[sz*4];

void build(int node,int b,int e)
{
    if(b==e)
    {
        tr[node] = a[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = tr[lft] * tr[rgt];
}

int query(int node, int b, int e, int i, int j)
{
    if(i<=b and e<=j) return tr[node];

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return (query(lft,b,mid,i,j) * query(rgt,mid+1,e,i,j));
}

void update(int node, int b, int e, int idx, int val)
{
    if(b==e)
    {
        a[idx] = val;
        tr[node] = val;
        return;
    }
 
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;

    if(idx<=mid)
        update(lft,b,mid,idx,val);
    else if(idx>mid)
        update(rgt,mid+1,e,idx,val);

    tr[node] = tr[lft] * tr[rgt];
}

int main()
{
    int n,q,x,y;
    char ch;
    string tst;

    while(cin>>n>>q)
    {
        tst = "";

        REP(i,n)
        {
            cin>>x;

            if(x>0) x=1;
            else if(x<0) x=-1;

            a[i+1] = x;
        }

        build(1,1,n);

        REP(i,q)
        {
            cin>>ch;
            if(ch=='C')
            {
                int idx,val;
                cin>>idx>>val;

                if(val>0) val = 1;
                else if(val<0) val = -1;

                update(1,1,n,idx,val);
            }
            else if(ch=='P')
            {
                cin>>x>>y;
                int res = query(1,1,n,x,y);
                if(res==0) tst+="0";
                else if(res>0) tst+="+";
                else tst+="-";
            }
        }
        pri(tst);
    }
    return 0;
}