クエリ先読みと 2D Binary Indexed Tree を用いる \(O((N^2+Q) (\log N)^2)\) の解法を紹介します。

この解法のポイントは、問題文中の守っているマスの条件 \((u-s)+\frac{(v-t)}{2}<M\) が \(2u+v-2M<2s+t\) のように変形することで両辺を「守られている」・「守っている」マスについて分離できるということです。

いま考えているクエリ \((X,Y)\) に対して、\(A_{s,t}=\) ( \(S_{s,t}=\) O かつ \(2X+Y-2M<2s+t\) なら \(1\) そうでなければ \(0\) ) となるような二次元配列 \(A\) を管理することにします。クエリに答える際は \(\sum_{s=1}^{X}\sum_{t=1}^{Y} A_{s,t}\) を出力すればよく、これは \(A\) を 2D Binary Indexed Tree で管理しておけば各クエリ \(O((\log N)^2)\) で行えます。

\(A_{s,t}\) の更新方法についてですが、与えられた順番にクエリを処理していくと更新を \(O(QN^2)\) 回行う必要が生じます。ここで、クエリを \(2X+Y\) の降順に処理することにすると、各 \(A_{s,t}\) の更新は高々 \(1\) 回しか起こらないので全体での変更回数が \(O(N^2)\) で抑えられます。

以上より \(A_{s,t}\) の更新に \(O(N^2 (\log N)^2)\)、クエリ回答に \(O(Q (\log N)^2)\)、合わせて\(O((N^2+Q) (\log N)^2)\) の解法となります。