6139:Interval Product

問題文
https://icpcarchive.ecs.baylor.edu/external/61/6139.pdf

数列とクエリが与えられる。クエリは以下の2種類である。

C a b 数列のa番目をbに更新する。
P a b 数列の区間[a,b]の積が負であれば-、0であれば0、正であれば+を出力する。

セグメント木を実装した。各ノードには
その区間の積が負ならば-1、0ならば0、正ならば1
という情報を持たせた。

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
const int max_n=1<<17;
 
int n,dat[max_n*2];
 
void init(int n_){
    n=1;
    while(n<n_)n*=2;
    for(int i=0;i<2*n;i++)dat[i]=0;
}
 
void update(int k,int a){
    k+=n-1;
    if(a>0)dat[k]=1;
    if(a==0)dat[k]=0;
    if(a<0)dat[k]=-1;
    while(k>0){
        k=(k-1)/2;
        dat[k]=dat[k*2+1]*dat[k*2+2];
    }
}
 
int query(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)return 1;
    if(a<=l && r<=b)return dat[k];
    else{
        int vl=query(a,b,k*2+1,l,(l+r)/2);
        int vr=query(a,b,k*2+2,(l+r)/2,r);
        return vl*vr;
    }
}

int main(void){
     
    int N,K;
    while(cin >> N >> K){
         
        init(N);
         
        for(int i=0;i<N;i++){
            int in;
            cin >> in;
            update(i,in);
        }
         
        for(int i=0;i<K;i++){
            char ch;
            int a,b;
            cin >> ch >> a >> b;
            if(ch=='C')update(a-1,b);
            else if(ch=='P'){
                int res=query(a-1,b,0,0,n);
                if(res==0)cout << 0;
                else if(res>0)cout << '+';
                else if(res<0)cout << '-';
            }
        }
        cout << endl;
    }
     
    return 0;
}