読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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;
}