Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12436 - Rip Van Winkle's Code (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12436

問題概要

問題文でコードと同じ動作をするもっと速いコードを書けという問題.
配列のサイズを250000以下として,以下のクエリ(最大400000個)に答えられれば良い.
 A ある区間[st, ed]を指定して,data[st] += 1; data[st+1] += 2; ... data[ed] += ed-st+1;と階段状に足す.
 B ある区間[st, ed]を指定して,data[st] += ed-st+1; data[st+1] += ed-st; ... data[ed] += 1;と階段状に足す.
 C ある区間[st, ed]を指定して,その区間の要素を全部xに変更する.
 D ある区間[st, ed]の和を求める.

解法

セグメントツリー+遅延評価.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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