Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11992 - Fast Matrix Operations (この記事を編集する[管理者用])

Source

Rujia Liu's Present 3: A datastructure contest celebrating the 100th anniversary of Tsinghua University (2011-04-23) (blog)
UVa 11992

問題概要

要素数10^6,ただし行数が20以下の行列を考える.
最初は全部の要素が0.
以下の操作を行う問題.操作の回数は最大で20000回以下.
最終的に,行列の全要素の和は10^9を超えないことが保証されている.
 1. ある長方形部分の各要素にvだけ足す
 2. ある長方形部分の各要素をvにする
 3. ある長方形部分の各要素の和と,最小要素の値と,最大要素の値を求める

解法

行数がたかだか20しかないので,各行に対してsegment treeを作る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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