固定された \(k\) について問題を解くことを考えます．

\(A_i\leq B_i\) を仮定して一般性を失いません．区間 \([A_i,B_i]\) の端点からどちらかを選ぶというように問題を言い換えます．

はじめに、\(C_1\) を \(A_1,B_1\) のどちらにするかは両方試すこととします．

このとき、区間 \([A_i,B_i]\) が \(C_1\) を含まないような \(i\) については、\(C_i\) をどちらにするのが最適かが一意に定まります．\(C_i\) が確定すると、更に別の区間 \(j\) についても \(C_j\) が一意に定まることもあります．これを可能な限り繰り返します．

上の手続きが終了すると、既に確定した \(C\) の最小値を \(m\) 、最大値を \(M\) とすると、\(C_i\) が定まっていない区間について以下の条件が成り立つことが確認できます．

• \(A_i\leq m \leq M \leq B_i\)

ここで残った区間について、包含関係にあるようなものがあれば、その内側の区間は無視してもいいことが分かります．より具体的に言えば、区間 \(i,j\) が

• \(A_i\leq A_j\leq B_j\leq B_i\)

を満たすならば、\(C_i=A_i\) の場合 \(C_j=A_j\) に、\(C_i=B_i\) の場合 \(C_j=B_j\) とするのが最適なので、内側の区間は考慮しなくてもよいです．

包含関係にあるような内側の区間は考慮しなくてもいいことが分かったので、残った未確定の区間は全て交差関係にあります．残った区間を \((L_1,R_1),\ldots,(L_x,R_x)\) とすると、以下の形で書き表せます．

• \(L_1\leq L_2\leq \ldots \leq L_x\leq m \leq M \leq R_1\leq R_2\leq \ldots\leq R_x\)

ここまでくれば最小値を求めるのは簡単で、答えは \(\min(\min_{i=1,2,\ldots,x-1}(R_{i}-L_{i+1}), M-L_1,R_x-m)\) と分かります．

ここまでの議論を用いると、\(k\) が動く場合も簡単に対応できます．

情報として管理する必要があるのは、交差関係にある区間の集合 \(((L_1,R_1),\ldots,(L_x,R_x))\) 及び \(R_{i}-L_{i+1}\) の最小値でした．

\(k\) が \(1\) 増えることで起きるのは、区間の集合への区間の追加、削除のみです．そのため、区間の集合と \(R_{i}-L_{i+1}\) の集合を std::set などで管理することで、効率的に更新に対応することができます．

計算量は \(\mathrm{O}(N\log N)\) です．