範例程式碼 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");
}
}