Interval Product (UVa 12532, UVaLive 6139, Regionals 2012 >> Latin America)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int z1, z2, node[MX*4]; void insert(int idx, int st, int ed, int s, int e, int val) { if(st==s && ed==e) { if(val>0) node[idx]=1; else if(val<0) node[idx]=-1; else node[idx]=0; return; } int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1; if(e<=mid) insert(lft, st, mid, s, e, val); else if(s>mid) insert(rgt, mid+1, ed, s, e, val); else { insert(lft, st, mid, s, mid, val); insert(rgt, mid+1, ed, mid+1, e, val); } node[idx] = node[lft] * node[rgt]; return; } int query(int idx, int st, int ed, int s, int e) { if(st==s && ed==e) { return node[idx]; } int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1; if(e<=mid) return query(lft, st, mid, s, e); else if(s>mid) return query(rgt, mid+1, ed, s, e); else return query(lft, st, mid, s, mid)*query(rgt, mid+1, ed, mid+1, e); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc,kk=1, n, q, x, y; char c; string s; while(cin>>n>>q) { for(int i=1;i<=n*4;i++) node[i]=1; for(int i=1; i<=n; i++) { cin>>x; insert(1, 1, n, i, i, x); } while(q--) { cin>>c>>x>>y; if(c=='C') insert(1, 1, n, x, x, y); else { z1 = query(1, 1, n, x, y); //cout<<z1.pos<<" "<<z1.neg<<" "<<z1.zero<<endl; if(z1==0) cout<<"0"; else if(z1<0) cout<<"-"; else cout<<"+"; } } cout<<endl; } return 0; }