Uva:11992 Fast Matrix Operations

部内プロコンの解きこぼし

問題↓

Problem F: Fast Matrix Operations

問題概要

  • R * C の中身の値が全て0のグリッドが与えられます。
  • (x1,y1) - (x2,y2) の短形区間に対し次の操作を行えます。
  1. 区間に対し値を一様に加える
  2. 区間に対し値を一様に上書きする。
  3. 区間に存在する値の合計、最小値、最大値を出力する
  • R<=20(これ重要) , R*C <= 10^6,  M <= 20000 で上記のクエリがM回きます。 

解法

  • 区間に対し、値の更新、加算、合計値取得、最小値取得、最大値取得が行えるセグメントツリーを20個作る
  • REしないようにテストケースごとに配列のsegtreeの配列の値はresizeしてやる
ソースコード

感想

大真面目にセグメントツリーと睨めっこしたのは春合宿以来かもしれない。

遅延評価のなんたるかと実装法が分かったので良かった。(今までうろ覚えだった…)

ただ、コンテスト中にこれ自力で書けと言われるときつそうなのでライブラリ化したほうがいいのかもしれない