範例程式碼 uva12532

//uva12532
#include<bits/stdc++.h>
using namespace std;
int n[100005]; // 儲存某區間的負數之個數
// 最多為100000個，多宣告一些以避免產生可能邊界問題邊界問題
int zero[100005]; // 儲存某區間的0之個數

void add(int *s,int h,int x){
	for(int i=h;i<100005;i+=i&-i){
		s[i]+=x;
	}
}
// s[1]儲存1..1之和，s[2]儲存1..2之和，s[3]儲存3..3之和，s[4]儲存1..4之和
// s[5]=5..5, s[6]=5..6, s[7]=7..7, s[8]=1..8, 
// s[9]=9..9, s[10]=9..10, s[11]=11..11, s[12]=9..12
// s[13]=13..13, s[14]=13..14, s[15]=15..15, s[16]=1..16 
// i&-i 找出最右邊1之位置，例如 6&-6=6 &(-6) =2
// i+=i&-i，以i=h=1為起始，計算順序為1, 2, 4, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=2為起始，計算順序為2, 4, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=3為起始，計算順序為3, 4, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=4為起始，計算順序為4, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=5為起始，計算順序為5, 6, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=6為起始，計算順序為6, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=7為起始，計算順序為7, 8, 16, 32, 64 ...
// i+=i&-i，以i=h=8為起始，計算順序為8, 16, 32, 64 ...

int presum(int *s,int h)
// prefix sum, that is, q[1]+q[2]+...+q[h]
{
	int res=0;
	for(int i=h;i>0;i-=i&-i){
		res+=s[i];
	}
	return res;
}
//i-=i&-i，以i=h=15為起始，計算順序15, 14, 12, 8。
// 也就是將以下範圍相加： 15..15, 13..14, 9..12, 1..8
//i-=i&-i，以i=h=10為起始，計算順序10, 8。
// 也就是將以下範圍相加： 9..10, 1..8

int main(){
	int n,k;
	while(scanf("%d %d",&n,&k)!=EOF){
		memset(n,0,sizeof(n));
		memset(zero,0,sizeof(zero));
		int a[100005];
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(a[i]==0)
			    add(zero,i,1);
			else if(a[i]<0)
			    add(n,i,1);
		}
		while(k--){
			char c[2];
			scanf("%s",c);
			if(c[0]=='C'){
				int i,j;
				scanf("%d %d",&i,&j);
				if(a[i]<0)
				    add(n,i,-1);
				else if(a[i]==0)
				    add(zero,i,-1);
				a[i]=j;
				if(a[i]<0)
				    add(n,i,1);
				else if(a[i]==0)
				    add(zero,i,1);
			}
			else{
				int left,right;
				scanf("%d %d",&left,&right);
				int neg=presum(n,right)-presum(n,left-1);
				// 計算left..right之個數 
				int ze=presum(zero,right)-presum(zero,left-1);
				if(ze)
				    printf("0");
				else if(neg&1)  // neg % 2
				    printf("-");
				else
				    printf("+");
			}
		}
		printf("\n");
	}
}