\(e_i = 1\) または \(e_i=2\) の場合

まず、\(e_i=0\) であるような条件が存在しない場合の解法を考えます。この時、\(X\) の要素として \(0\) を使う理由が無いため、すべての要素は \(1\) または \(2\) であるとして良いです。また、いくつかの \(1,2\) の積を \(3\) で割った余りについて検討すると、\(2\) の個数が偶数ならば \(1\) に、奇数ならば \(2\) になります。
以上を踏まえ、\(y_{i,j}\) を次のように定めます。

• \(x_{i,j}=1\) ならば \(y_{i,j}=0\)、\(x_{i,j}=2\) ならば \(y_{i,j}=1\)

条件を表す変数のうち \(e_i\) についても同様のことを考えると、この問題は \(N^2\) 個の変数に対する \(F_2\) 上の連立方程式を解く問題になります。 (この連立方程式に解が存在しない場合、答えは No となります) 変数が \(A\) 個、式が \(B\) 個存在する \(F_2\) 上の連立方程式は、bitsetを用いた掃き出し法によって \(\mathrm {O}(\frac{AB^2}{w})\) で解くことが出来ます( \(w\) はワードサイズ)。しかし、\(A=N^2, B=Q\) とすると実行時間制限に間に合いません。そこで、長方形領域の総和を得る方法として二次元累積和の手法を考えると、変数の個数を \(4Q\) 個に減らすことが出来、十分高速になります。

元の問題の解法

\(e_i=0\) である条件が存在する場合においても、\(e_i=1,2\) である条件で指定されている範囲内の要素を \(0\) にすることは出来ません。一方、\(e_i=1,2\) である条件で指定されていない要素は \(0\) にしても損をしません。ゆえに、\(e_i=1,2\) である条件のみを考えた状態で先の解法を用いて \(X\) を構築し、\(e_i=1,2\) である条件で指定されていない要素を \(0\) にするのが正当です。(これで \(e_i=0\) である条件が満たされない場合、答えは No となります)