Codeforces Round 522 (Technocup 2019 Elimination Round 3)

A. Barcelonian Distance

始点，終点の bounding box をとり，bounding box と直線の交点を経由値の候補とすればよいです．

クエリ集合を $S$，それ以外を $T$ として，$S,T$ のうち種類数が $2$ 以上であるものに含まれるものは特定不可能です．

全体集合の種類数が $2$ 以下ならば，その方法ですべて特定可能です．$3$ 以上ならば，特定可能なのは高々 $1$ 種類ということになります．

$a$ を $b$ 個という質問で特定可能であるかは，$b$ 個で $ab$ を作る方法の数え上げを dp で求めておけば確認できます．

条件は，「$2$ 頂点以上の連結成分はすべて完全マッチングを持つ」となります．あとは素直に木DPをすればよいです．

円環ではなく，長さ無限大で周期 $N$ の列だと思って置きます．

$\{v\}$ からはじめて $m$ 回操作したときの区間を $[L_{m,v},R_{m,v}]$ とすると， $\{a,a+1,\ldots,b\}$ から始めた場合には $[\min_{a\leq v\leq b}L_v,\max_{a\leq v\leq b}L_v]$ になります．

よって，セグメント木区間クエリと binary lifting で解くことができます．

なんと出題から $7$ 年経った時点でジャッジに間違いがあって，苦労させられました（修正済）．

まず，$32$ 桁になるように $0$ 埋めします．このためには，’0′ はコピー，’1′ はコピー，空は ‘0’ になるようにします．

次を使いました：”d1usssd0ussssttt”

下のマスに書かれた値が時刻順に …11110000…. のようになるようにして，注目しているマスの値によって適切な量を巻き戻す調整をしています．

あとは $1$ の位から順に処理していきます．$c$, $a$, $b$ が上から下に並んでいるときに，$c$ の左に $\lfloor (c+a+b)/2\rfloor$ を書いて（繰り上がり），$b$ の下に $(c+a+b)\bmod 2$ を書いて，

どちらもマス $x$ に居て，$x,a,b,c$ が隣接しているとき，

…., $x\to a$, $s$, $a\to b$, $s$, $b\to c$, $s$, $t,t,t\ldots$

の要領で調整できます．最初の … の部分でマス $x$ に時刻ごとの値を適当に決めておきます．