UVa 12532 : Interval Product
問題リンク:http://uva.onlinejudge.org/external/125/p12532.pdf
問題概要:
n個の要素をもつ配列A[i](0 <= i <= n-1)とK個のクエリーが与えられる
クエリーは以下の形式からなる
1. C I J
2. P I J
1.の時、配列Aの要素Iを値Jに変更する
2.の時、要素A[I-1]からA[J-1]までの積(つまり、A[I-1] * A[I] * A[I+1] * ... * A[J-1])が正なら"+"と、負なら"-"と、0なら"0"と出力する
解法:
RMQかFenwickTree(BIT)を使用する
今回は蟻本のRMQを変更して使用した
あとはその通り処理する
!!!気をつける点!!!
積が0の時、0と出力する亊
oではない
pdfではoに見える
こんなミスをするのは、自分だけだろうが・・・
コード:
//RMQは蟻本のやつの改良 int N,Q; int A[MAX_N]; int main() { while(cin >> N >> Q) { RMQ_segment<int> rmq; rmq.init(N); rep(i,N) { cin >> A[i]; rmq.update(i,A[i]); } //rmq.print(); char opr; int I,J; rep(_,Q) { cin >> opr >> I >> J; I--; if(opr == 'C') { rmq.update(I,J); } else { int res = rmq._query(I,J); if(res > 0)printf("+"); else if(res == 0)printf("0"); else printf("-"); } } puts(""); } return 0; }