Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

COJ 1590 - Jupiter Attacks! [JUPITER] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1590 [JUPITER]

問題概要

数列 a0, a1, a2, ..., an に対して,以下の形のハッシュを考える.
 a0 * B^n + a1 * B^(n-1) + ... + an * B^0 mod P
Pは与えられた素数で,Bは与えられた整数.
長さL (10^5以下) の数列で,最初は全部0のものがある.
クエリがN個 (10^5) 与えられるのでそれに答える問題.クエリの形式は以下のとおり.
 クエリ1: 数列のある1つの要素を,ある値に変更する
 クエリ2: 数列の連続する部分列を1つ指定して,そのハッシュを求める.

解法

平方分割で解いた.Segment treeでもOKだと思う.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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