ABC177 F. I hate Shortest Path Problem

概要

縦H+1マス、横Wマスのマス目がある。
最初、一番上のいずれかのマスからスタートし、右または下に1マスずつ移動していくことを繰り返す。
ただし、上から1以上H以下の縦iマスの左からA_i～B_iマスについては、下に移動することができない。

上からi (i=1～H)のマスのいずれかに移動するための最小移動回数を求めよ。
ただし、移動できない場合は-1を出力せよ。

制約

• 1 <= H, W <= 2 * 10^5
• 1 <= A_i <= B_i <= W

解法

(遅延セグメント木解)

indexが0～Wまである配列を考える。
問題文は、A_i, B_iが与えられたら、A_i-1の値がxだとしたら、A_iマスはx+1、A_i +1マスはx+2、・・・のようにindexに対して等差(公差は正)になるように範囲更新できればよい。
例としては、

最初：0 0 0 0 0 0
↓
(A_i, B_i)=(1,3)、x=1が与えられる
↓
0 1 2 0 0 0

のように更新できれば、1段下に下がったときの各マスへの横方向への移動距離がわかる。
求めたい答えは、全体での最小値で、範囲最小値が取得できれば、それに縦方向の移動距離iを足したものが答えになる。

したがって、

• 範囲等差(公差は正)更新
• 範囲min

ができればよい。
これを遅延セグメント木で考える。

遅延セグメント木において、モノイドSに対して作用素Fが適用される場合を考える。

「範囲等差(公差は正)更新」は、位置が依存しているので、単純にSが「範囲の最小値」だけを保持しているだけでは、FがSに作用したときのSの更新ができない。
(足りない情報としては、「Fの左端」と「Sの左端」の情報がないので、Fの範囲で左からx、x+1、x+2、・・・とした場合、Sの左端の位置でのx+?がわからないので、Sの範囲での最小値がわからない。)

そこで、SとFに「範囲(左端indexと右端index)」を情報ともたせると、位置に依存した計算を行うことができる。

具体的には、

• Sは「範囲min」「そのSが扱う範囲(左端index, 右端index)」(この問題では右端は不要)
• Fは「Fの左端での値x」「そのFが適用される範囲(左端index, 右端index)」(この問題では右端は不要)

をもたせる。
(図ではそれぞれの「l」と「r-1」の情報。半開区間で[l, r)のほうがよさそう)

FがSに作用した場合、Sの範囲の一番左の値は「F.x + (S.l-F.l)」で更新できる。
(Sの範囲の一番右の値も「F.x + (S.r-1-F.l)」でわかる)
Sの範囲で一番小さい値は、(公差が正なら)一番左の値になるので、結局Sのminは「F.x + (S.l-F.l)」で更新すれば良い。

また、SとS'からS''を計算する場合は、

• 範囲minは、SとS'の範囲minの値で小さい方
• S''の扱う範囲は、S.lからS'.r-1まで

とわかるので、そのように計算すれば良い。

static const ll INF = (ll)(1e15);

struct S {
  ll val;
  ll range_l, range_r;
};
struct F {
  ll x;
  ll range_l, range_r;
};

S op(S l, S r){
  S ret;
  ret.val = min(l.val, r.val); //範囲min

  ret.range_l = min(l.range_l, r.range_l); //左端
  ret.range_r = max(l.range_r, r.range_r); //右端
  return ret;
}
S e(){
  return S{INF,-INF,INF};
}
S mapping(F l, S r){
  if(l.x == INF) return r;
  return S{l.x+(r.range_l-l.range_l), r.range_l, r.range_r}; //範囲minをSの左端の値にする
}
F composition(F l, F r){
  if(l.x == INF) return r;
  return l;
}
F id(){
  return F{INF,-INF,INF};
}

コード的には、

  int H, W;
  cin >> H >> W;
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(W+1);
  rep(i,W+1){ seg.set(i, S{0,i,i+1}); } //最初は0で初期化
  seg.set(0, S{W+1,0,1}); //index=0だけはW+1(移動できない)にしておく

  rep(i,H){
    int A, B;
    cin >> A >> B;
    {
      S s = seg.get(A-1);
      seg.apply(A-1, B+1, F{s.val,A-1,B+1}); //A-1～Bで範囲等差更新(左端の値を指定)
    }
    {
      S s = seg.all_prod(); //全範囲での範囲min
      if(s.val != W+1) cout << s.val+(i+1) << endl; //移動できる場合は、「横方向移動距離＋縦方向移動距離」を出力
      else cout << -1 << endl;
    }
  }

反省

「SとFに範囲情報を持たせる」は汎用的そうで、「範囲f(x,i)更新」とかも同様に扱える。