12532 - Interval Product

IntervalProduct.cpp

#include <bits/stdc++.h>
using namespace std;
int N,K;
int List[100002]={0};
int BIT1[100002]={0};
int BIT2[100002]={0};
void update(int* A, int idx, int val){
	while(idx<=N){
		A[idx]+=val;
		idx += (idx&(-idx));
	}
}
int query(int *A, int idx){
	int s = 0;
	while(idx){
		s+=A[idx];
		idx -= (idx&(-idx));
	}
	return s;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a,b,i,num;
	char op;
	while(cin>>N>>K){
		memset(List, 0, sizeof(List));
		memset(BIT1, 0, sizeof(BIT1));
		memset(BIT2, 0, sizeof(BIT2));
		for(i=1; i<=N; ++i){
			cin>>num;
			if(num<0){
				update(BIT2,i,1);
			}
			else if(num == 0){
				update(BIT1,i,1);
			}
			List[i]=num;
		}
		for(i=1; i<=K; ++i){
			//cout<<"\n>"<<i<<": ";
			cin>>op;
			cin>>a>>b;
			if(op == 'C'){
				if(b<0){
					if(List[a]>=0){
						update(BIT2, a, 1);
					}
					if(List[a] == 0){
						update(BIT1, a, -1);
					}
				} else if(b == 0){
					if(List[a] != 0){
						update(BIT1, a, 1);
					}
					if(List[a] < 0){
						update(BIT2, a, -1);
					}
				} else {
	               if(List[a] < 0){ 
	               		update(BIT2, a, -1); 
	               	}
	               if(List[a] == 0){ 
	               		update(BIT1, a, -1); 
	               	}
				}
				List[a] = b;
			} else {
				int lf = query(BIT1, a-1);
				int rg = query(BIT1, b);
				int dif = (rg-lf);
				if( dif >0 ){
					cout<<"0";
				} else {
					lf = query(BIT2, a-1);
					rg = query(BIT2, b);
					dif = rg-lf;
					if(dif%2){
						cout<<"-";
					} else {
						cout<<"+";
					}
				}
			}
		}
		cout<<endl;
	}
	return 0;
}