問題概要
（筆者は問題を要約することに疲れたようです）
考えたこと
$ X_i $ の範囲を絞る
$ L_i \leqq X _ {A_i} + X _ {B_i} \leqq R_i $ に着目する。
$ X_i $ のとり得る範囲を $ L ^ X _ i \leqq X_i \leqq R ^ X _ i $ とする。
仮に $ X _ {B_i} $ の範囲を $ \overline { L ^ X _ {B_i} } \leqq X _ {B_i} \leqq \overline { R ^ X _ {B_i} } $ に固定したとして考えるとき、$ X _ {A_i} $ は
$ L_i \leqq L ^ X _ {A_i} + \overline { R ^ X _ {B_i} } $
$ R ^ X _ {A_i} + \overline { L ^ X _ {B_i} } \leqq R_i $
を満たす必要がある。つまり、 $ X _ {A_i} $ の下限値は $ max ( L ^ X _ {A_i} , \, L_i - \overline { R ^ X _ {B_i} } ) $ に更新され、上限値は $ min ( R ^ X _ {A_i} , \, R_i - \overline { L ^ X _ {B_i} } ) $ に更新される。
すべての $ i $ に対して $ \lbrace L ^ X _ i , \, R ^ X _ i \rbrace = \lbrace 0 , \, M \rbrace $ で初期化し、BFS（あるいはDFS）を用いて $ L ^ X _ i , \, R ^ X _ i $ を更新することを繰り返すと、条件を《 なんとなく 》満たすような $ X_i $ の範囲が求まる。
また、この過程で $ L ^ X _ i > R ^ X _ i $ となるような $ i $ が存在するとき、題意を満たす整数列 $ X $ は存在しない。
上限値と下限値の平均を考える
求まった範囲に関して、$ X _ {A_i} , \, X _ {B_i} $ の範囲をそれぞれ固定したとして考えてみると、
$ L_i \leqq L ^ X _ {A_i} + R ^ X _ {B_i} \leqq R_i $
$ L_i \leqq L ^ X _ {B_i} + R ^ X _ {A_i} \leqq R_i $
が成り立つことがわかる。これらの平均をとると、
$$ L_i \leqq \dfrac { L ^ X _ {A_i} + R ^ X _ {A_i} } { 2 } + \dfrac { L ^ X _ {B_i} + R ^ X _ {B_i} } { 2 } \leqq R_i $$
となる。よって、《 平均値が整数なら 》その値を $ X_i $ とすればよい。問題となるのは平均値が整数でない場合である。
$ \dfrac { L ^ X _ i + R ^ X _ i } { 2 } = Ave ( i ) $ とおく。
$ Ave ( A_i ) , \, Ave ( B_i ) $ のいずれか一方のみが小数であるとき、(1) は [整数] $ \leqq $ [小数] $ \leqq $ [整数] となることから、$ X_i = \lfloor Ave ( i ) \rfloor , \, \lceil Ave ( i ) \rceil $ のどちらでもよい。
したがって、両方ともに小数であるときのみを考えればよい。
$ Ave ( i ) $ の小数部分は $ 0.5 $ であるから、
$ L_i \leqq \lfloor Ave ( A_i ) \rfloor + \lceil Ave ( B_i ) \rceil \leqq R_i $
$ L_i \leqq \lceil Ave ( A_i ) \rceil + \lfloor Ave ( B_i ) \rfloor \leqq R_i $
は常に成り立つ。
2-SAT への帰着
結局のところ、
$ ( X _ { A_i } = \lfloor Ave ( A_i ) \rfloor ) \, \land \, ( X _ { B_i } = \lfloor Ave ( B_i ) \rfloor ) $
$ ( X _ { A_i } = \lceil Ave ( A_i ) \rceil ) \, \land \, ( X _ { B_i } = \lceil Ave ( B_i ) \rceil ) $
が成立するかどうかを判定し、成立しない部分を 2-SAT にぶち込んでしまえば、題意を満たす整数列 $ X $ が存在するか判定できる。
例えば $ L_i > \lfloor Ave ( A_i ) \rfloor + \lfloor Ave ( B_i ) \rfloor $ であるとき、$ X _ { A_i } , \, X _ { B_i } $ にどんな値を代入しようとも $ ( X _ { A_i } > Ave ( A_i ) ) \, \lor \, ( X _ { B_i } > Ave ( B_i ) ) $ を満たす必要があり（もう一方も然り）、これらの論理式を充足できなければ当然に整数列 $ X $ は存在し得ないため、$ Ave ( i ) $ 近傍のみを見るだけで充分であると言える。
計算量
BFS（あるいは DFS）で $ X_i $ の範囲を絞るパートが一番重く、$ O ( ( N + Q ) M ) $ である（ $ X_i $ の範囲が更新される回数は高々 $ M $ 回）。
2-SAT のパートは、頂点数 $ O ( N ) $、辺数 $ O ( Q ) $ より $ O ( N + Q ) $ になる。
おそらく想定解より定数倍が相当軽い実装になっていると思われる。
