Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2378-70ee3599
この記事にトラックバックする(FC2ブログユーザー)

UVa 12532 - Interval Product (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12532

問題概要

N要素 (100000以下) の整数列Aが与えられる.各要素は-100以上100以下.
K個 (100000以下) のクエリに答える問題.各クエリは以下の2種類のうちのどちらか.
 C i v : A[i]をvに変更する
 P i j : A[i]*A[i+1]*...*A[j]が正か負か0かを求める

解法

Fenwick Treeを2つ使って,各区間の0の数,負の数の数を覚えておく.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2378-70ee3599
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。