F を [0,2],[0,3],[0,5]→[0,2],[2,3],[3,5] みたいに掃き出していくアルゴリズムの雑な計算量解析
各行に対し、ポテンシャル log(r-l+1) を考えると償却できる
1 つの列について掃き出したとき、ポテンシャルが 1 未満しか減らないことは高々 log(N) 個の行についてしか起こらないため
— 熨斗袋 (@noshi91) 2020年2月16日

A := 各スイッチが変化させる爆弾の行ベクトルを並べた F_2 上の M×N 行列
xA=0 なる M 次元ベクトル x を求めたい
A に対する行基本変形は基本行列を左から掛けるから、繰り返しの行基本変形は
xP⁻¹Q⁻¹R⁻¹RQPA=0
のように変形してると解釈できる
y := xP⁻¹Q⁻¹R⁻¹, B := RQPA
とすれば、(続)
— 熨斗袋 (@noshi91) 2020年2月17日

yB=0
B は基本変形の結果単純な行列になっており、y は簡単に求まるはずである
ここで y の定義式に RQP を右から掛けて
x = yRQP
を得る
すなわち、得られた y に基本行列を逆順に右から掛ければ x が得られる
ベクトルに基本行列を乗じることは Θ(1) で可能で、解が得られた
書いてないため嘘かも
— 熨斗袋 (@noshi91) 2020年2月17日

僕はコンテスト中に掃き出し法を頑張っていたのですが、関与するスイッチを全部vectorに持って大爆発しました。ところが、それが計算量保証もついて復元もできるそうです。このブログ記事では上の3つのツイートを自分なりに解釈し、ACコードの解説をします。

簡単のため、以下では

爆弾は座標の昇順にソートされている
スイッチ $i$ は番号 $[L_i,R_i)$ (1-indexed) の爆弾のオン・オフを切り替える

というふうに順番の入れ替え・座標圧縮が行われているとします。

問題の言いかえ

サンプル1を例にとります。

爆弾を座標の昇順にソートします。それぞれの $B$ の値を並べた行ベクトルを $\vec{ b }=( B_1, B_2, B_3 )=(1,0,1)$ とします。

スイッチはそれぞれ $[L_1,R_1)=[1,4),[L_2,R_2)=[1,2),[L_3,R_3)=[2,2),[L_4,R_4)=[2,3)$ となります。ここで、3番目のスイッチはどの爆弾にも関係しませんが、座標の大小関係を見て $L_3=R_3=2$ としておきました。

さて、各スイッチに対して、3次元の行ベクトルを以下のように定めます：第 $L_i$ 列から第 $R_i-1$ 列は1、それ以外は0を要素に持つ。

すると順に $(1,1,1),(1,0,0),(0,0,0),(0,1,0)$ となります。これを縦に積み重ねた $4 \times 3$ 行列を

とします。

これが元ツイートに言う「 $A$ を、各スイッチが変化させる爆弾の行ベクトルを並べた $\mathbb{F}_2$ 上の $M \times N$ 行列とする」です。

そして元の問題は、 $\mathbb{F}_2$ 上で（i.e. 加算を $\oplus$ としたときに） $\vec{x}A=\vec{b}$ を満たす $M$ 次元行ベクトル $\vec{x}$ を構成せよ、と言いかえることができます。

サンプル1では $\vec{x}=(1,0,0,1)$ となります。実際に確認してみます。

$\vec{x}A=\vec{b}$ を解く

まず行基本変形によって $A$ を掃き出し、単純な形にします。演算は $\mathbb{F}_2$ 上で行います。

第2行を第1行に足す

第4行を第1行に足す

の2回の操作でそこそこ単純らしい形になります。行の入れ替えをしないのは実装上の都合です。

変形後の行列を $A'$ とします。 $\vec{x'}A'=\vec{b}$ は簡単に解けて、

より $\vec{x'}=(1,1,0,0)$ です。この $\vec{x'}$ から $\vec{x}$ を復元します。

そもそも、行基本変形はそれぞれ $M \times M$ の基本行列を左から掛けることによって行われるのでした。今回は2回操作を行ったので、それぞれに対応する基本行列を $P_1,P_2$ とおくと、 $P_2P_1A=A'$ です。

$\vec{x'}A'=\vec{x'}P_2P_1A=\vec{b}=\vec{x}A$ より $\vec{x}=\vec{x'}P_2P_1$ が得られます。

基本行列を右から行ベクトルに掛けるとどのような変換が行われるのかを、 $P_1$ を例にして観察します。

$P_1$ は第2行を第1行に足す操作です。単位行列の $(1,2)$ 成分が1になったものですから、

第1列を第2列に足す操作になりました。

これを見ると、行列に対する「第 $i$ 行を第 $j$ 行に足す」という操作は行ベクトルにおいて「第 $j$ 列を第 $i$ 列に足す」という操作である、ということが言えます。これを念頭に置いて、

第1列を第4列に足す
$\vec{x'}P_2=(1,1,0,0)P_2=(1,1,0,1 \oplus 0)=(1,1,0,1)$
第1列を第2列に足す
$\vec{x'}P_2P_1=(1,1,0,1)P_1=(1,1 \oplus 1,0,1)=(1,0,0,1)$

より $\vec{x}=\vec{x'}P_2P_1=(1,0,0,1)$ が得られました。これは正しいです。

解法のまとめと実装に際しての注意

まとめると、次のようなアルゴリズムになります。

まず行列 $A$ を作り、「第 $i$ 行を第 $j$ 行に足す」操作を繰り返して単純な形にします。次に、その状態での答え $\vec{x'}$ を作ります。最後に、 $A$ に行った操作を逆順に巻き戻して $\vec{x}$ を復元します。

さて、これまで出てきた行列はどれも行・列のサイズが 10⁵ オーダーの巨大なものなので、何らかの工夫をしてデータを圧縮しなければなりません。幸い、基本行列の操作は先の観察から $(i,j)$ のペアによって復元できることが分かっているので、問題は $A$ です。

ここで、最初の $[L_i,R_i)$ による表示に立ち戻ってみます。 $A$ とは、第 $i$ 行の第 $L_i$ 列から第 $R_i-1$ 列が1である行列でした。実は、列 $L$ について掃き出すとき、 $R_i\le R_j$ としてスイッチ $[L,R_i)$ と $[L,R_j)$ を $[L,R_i)$ と $[R_i,R_j)$ に変換する操作のみ考えればよいです。

この操作だけでは「各列に1である要素が1つずつしかない」ようにはできませんが、並び替えたときに対角線より下の要素がすべて0になるもの、つまり正方行列で言う上三角行列を作ることは可能です。このことは列に関する数学的帰納法で示せますが、もっと感覚的に言えば、掃き出し法で自分より上の行を無視すれば上三角行列になるということです。

またこのことから、各行の1の要素はすべて $[L_i,R_i)$ という区間で表せることがわかります。よってこれを保存すれば $A$ を表すことができます。

計算量解析

熨斗袋さんの1番上のツイートを解釈します。

まず初めに、掃き出す手順を固定します。列 $L$ について掃き出すとき、関係するスイッチたちが $[L,R_1),[L,R_2),\cdots,[L,R_k)\;(R_1\le R_2 \le\cdots\le R_k)$ であったとすると、これを $[L,R_1),[R_1,R_2),\cdots,[R_{k-1},R_k)$ に変換することにします。逆順に隣り合うペアを取り出し、掃き出すことで達成できます。

この操作を行ったとき、区間の幅が半分以上残るものは各列について高々 $O({\rm log}\;N)$ 個である、というのが重要な考察です。

区間の幅が半分以上残るものが $k$ 個であったとします。このとき、区間の幅の最大値を小さくすることを考えると、 $[0,1),[0,2),[0,4),[0,8),\cdots,[0,2^{k-1})$ を $[0,1),[1,2),[2,4),[4,8),\cdots,[2^{k-2},2^{k-1})$ に変換するのが最適だとわかりますが、これでも区間の幅 $2^{k-1}\le N$ が成り立つ必要があるため、 $k\le 1+{\rm log}_2\;N$ となるからです。

区間の幅の変化を、「半分以上残る」か否かの2通りに分け、それぞれの回数を評価します。

半分以上残る
各列について高々 $O({\rm log}\;N)$ 回、合わせると $O(N{\rm log}\;N)$
半分未満になる
「ちょうど半分になる」と言いかえれば上から評価できます。各スイッチについて、上の「半分以上残る」場合がなかったと仮定すると「ちょうど半分になる」ことは最大で $O({\rm log}\;N)$ 回起こるので、合わせて $O(M{\rm log}\;N)$