IOI 2014 Day1 - Wall
概要
Author: SSRS
解法
小課題 1
各列の高さを管理し、愚直にクエリを処理すればよい。
小課題 2
区間 chmin クエリ、区間 chmax クエリをそれぞれ処理できればよい。これは双対セグメント木を使えばできる。
小課題 3, 4
区間 chmin, chmax クエリをともに処理するデータ構造を考える。
区間 chmin, chmax クエリを何回か合成すると、$ f(x)=\min(\max(x, r), l)の形の関数になる。以下、この関数を$ \text{clamp}(x, l, r)と表す。
クエリを双対セグメント木を用いて高速に処理するためには、$ \text{clamp}(x, l, r)の形の関数を合成してもこの形の関数になればよい。実際、$ \text{clamp}(\text{clamp}(x,l_1, r_1), l_2, r_2)は以下のようになる。
$ r_1<l_2のとき、$ \text{clamp}(x, l_2, l_2)に等しい。
$ l_1>r_2のとき、$ \text{clamp}(x, r_2, r_2)に等しい。
どちらでもないとき、$ \text{clamp}(x, \max(l_1,l_2), \min(r_1,r_2))に等しい。
よって、双対セグメント木でクエリを高速に処理できる。時間計算量は$ O((N+Q)\log N)となる。
類題
$ \text{clamp}(x+a, l, r)の形の関数を合成する問題が出題されている。
応用的な話題であるが、Segment Tree Beats を用いると、上に加え区間の和を計算することもできる。ただし、OI コンテストで出題されることはほとんどない。