ABC128 E Roadwork
所感
やむと゛ぅ はちえんセク゛き をてにいれた！
やむと゛ぅ はさ゛あつ をてにいれた！
問題概要
N個の道路工事とQ人の人間が与えられる。道路工事はS, T, Xの形で与えられ、それぞれS-0.5 からT-0.5 の時間座標Xを道路工事し通行止めにすることを表す。
人間はdの形で与えられ、時刻dに座標 0を出発し速度1で正方向に歩く。
人間が道路工事に出会うまで歩くとき、各人間の歩く距離を求めよ。
取った方針
横軸t(時間)、縦軸x(座標)なるダイヤグラムを書くと、Q本の直線とN本の直線の交点のうちxがもっとも小さいものを求める問題になります。
もう少し考察すると、(S, T, X)で表される工事はdが[S-X, T-X)に含まれる人間にのみ影響することがわかるので、t軸において、N個の区間とそれに対応する値xが与えられ、座標dを被覆する区間[S-X, T-X)に対応するXの最小値を求める問題になります。
これは確かにセグ木で殴れそうですが区間更新ができることを知らず死亡
解いた方針
セグ木は遅延評価をすると区間更新ができるようになることが知られています。
セグ木の概念をグラフィカルに理解するならここ
http://tsutaj.hatenablog.com/entry/2017/03/29/204841
遅延セグ木の概念をグラフィカルに理解するならここ
http://tsutaj.hatenablog.com/entry/2017/03/29/204841
遅延セグ木を一般化するならここ
http://beet-aizu.hatenablog.com/entry/2017/12/01/225955
がよくて、最後の天才さんのライブラリを使いました。
理解するためにめちゃめちゃコメントを付けたので貼っておきます。
//出典 http://beet-aizu.hatenablog.com/entry/2017/12/01/225955 template <typename T, typename E> struct SegmentTree { typedef function<T(T, T)> F; typedef function<T(T, E)> G; typedef function<E(E, E)> H; typedef function<E(E, int)> P; int n; F f; G g; H h; P p; T d1; E d0; vector<T> dat; vector<E> laz; SegmentTree(int n_, F f, G g, H h, T d1, E d0, vector<T> v = vector<T>(), P p = [](E a, int b) {return a; }) : f(f), g(g), h(h), d1(d1), d0(d0), p(p) { init(n_); if (n_ == (int)v.size()) build(n_, v); } //初期化。要素配列と遅延配列を2*n-1個にする void init(int n_) { n = 1; while (n<n_) n *= 2; dat.clear(); dat.resize(2 * n - 1, d1); laz.clear(); laz.resize(2 * n - 1, d0); } //既存のvectorからセグ木を構築 void build(int n_, vector<T> v) { for (int i = 0; i<n_; i++) dat[i + n - 1] = v[i]; for (int i = n - 2; i >= 0; i--) dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]); } //ノードを評価する。 inline void eval(int len, int k) { //遅延配列に単位元が入ってたら評価済みなのでおしまい if (laz[k] == d0) return; //葉ノードでないなら遅延伝播する if (k * 2 + 1<n * 2 - 1) { //h: 2つの作用素を引数に取り合成した作用素を返す関数 laz[k * 2 + 1] = h(laz[k * 2 + 1], laz[k]); laz[k * 2 + 2] = h(laz[k * 2 + 2], laz[k]); } //p: このノードに対応する区間長と作用素を引数に取り、区間長に対応する作用素を返す関数 //dat[k] にlaz に溜めていた作用素を適用(g: 要素型と作用素型を引数に取り、要素に作用素を作用させた結果を返す関数、ここでの作用素とは区間Sum区間Addなら (+ 3) とか) dat[k] = g(dat[k], p(laz[k], len)); //適用し終わったので遅延配列をクリア laz[k] = d0; } //[l,r)の区間を再帰的に見ながら0-indexedの[a, b)を更新する T update(int a, int b, E x, int k, int l, int r) { //先に評価 eval(r - l, k); //範囲外ならなにもしないでそのノードが持つ値を返す if (r <= a || b <= l) return dat[k]; //完全被覆なら既に遅延配列に入っている作用素と追加したい作用素をマージした後にそれを要素に作用させた結果を返す、pは区間長に対応する作用素を得るための（ｒｙ if (a <= l && r <= b) { laz[k] = h(laz[k], x); return g(dat[k], p(laz[k], r - l)); } //完全被覆でも範囲外でもないなら(中途半端にかぶっているなら)完全被覆と範囲外の境界が見えるまで木を潜って変化後の値を得る return dat[k] = f(update(a, b, x, k * 2 + 1, l, (l + r) / 2), update(a, b, x, k * 2 + 2, (l + r) / 2, r)); } T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); } T query(int a, int b, int k, int l, int r) { eval(r - l, k); //範囲外なら単位元を返す if (r <= a || b <= l) return d1; //完全被覆ならそのまま返す if (a <= l && r <= b) return dat[k]; //一部被覆なら完全被覆と範囲外に分かれるまで木を潜る T vl = query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return f(vl, vr); } //0-indexedで[a, b)の区間*を求める T query(int a, int b) { return query(a, b, 0, 0, n); } };
抽象的な数学が書いてあってウワッとなるけど俺は頭がいいからわかるんだという気持ちで読むとわかる
一番難しいのは作用素のマージとかいう概念ですが、遅延配列lazに入っているのは値ではなく作用素(関数みたいなもの(まさかりを投げるな))が入っていて、新たにそのノードに作用素を作用させたくなったら溜まっている関数と合成するのじゃ、と考えると飲み込みやすい気がします
コンストラクタ引数でセグ木で使う演算を注入できて、それぞれ
int n_ 要素数。
f 2つの要素Tをマージするための関数。
g 1つの要素Tに作用素Eを適用するための関数。
h 2つの作用素Eをマージするための関数。
T d1 演算fの単位元。
E d0, g, hの単位元。
vector
P p 区間の長さbを引数に取り、区間の長さによって変化する作用素E'を返す関数。
であるので、今回は更新クエリがchmin で区間最小が知りたいので以下になります。
f: min
g: min
h: min
d1: INT_MAX
d0: INT_MAX
p : {return a; }(適用すべき作用素は区間の長さによらない)
これを用意すると区間chminクエリを処理したのち区間最小が求められるので、言い換えた問題が解けます。
ただし、tの範囲が109と広いので、このままセグ木を作るとMLEするので座標圧縮をします。
正しい方針(解説の方針)
問題を言い換えるところまでは同じ、imos法 っぽく始点と終点に注目して、始点でsetにxを追加、終点でsetからxを削除、って感じのことをする。
時刻d以下のクエリを消費し終わった時のsetの最小値が答え
得られた知見
・セグ木の一般化(作用素のマージ)
・座標圧縮
・ダイヤグラム->絵を描く
解くのに必要な要素
・セグ木 + 座標圧縮
・もしくはimos法 っぽいアレ
周辺調査によって得られた知見
・得られた知見 に包含される
