最近のABCのCとかD、普通にむずいんだよな
まず、1つの行や列に、黒と白両方が置かれることはない。
「●・・●・・・○」みたいな配置を考えたとき、 混在していると必ず黒と白の境界が存在するので、その部分の駒が互いの利きに入ってしまう。
なので、行と列をそれぞれ、以下のグループに分ける。
「黒のみ置かれる行数 $R_b$」「黒のみ置かれる列数 $C_b$」「白のみ置かれる行数 $R_w$」「白のみ置かれる列数 $C_w$」として これらを決め打ったとき、その行・列を $N \times M$ のどこに配置するかは、以下のようになる。
また、以下がわかれば、
全体の置き方の個数は、これらの積となる。
$R_b,C_b,R_w,C_w$ の全探索は $O(N^2M^2)$ で可能なので、あとは $f_b,f_w$ を前計算などで $O(1)$ で得られればよい。
重複を避けるため、$f_b,f_w$ は必ず空行・空列のない置き方で無いといけない。
B=3 Rb=3 Cb=2 OK NG NG 1つめのNGの置き方は、 ●・・ ●・・ ●●● Rb=2 Cb=2 を探索したときに既に数えられている ・●● ●●・ ・・・
重複を気にしなければ、$R_b \times C_b$ 個のマスの中から置く $B$ マスを選べば良いので、${}_{R_b \times C_b}C_{B}$。
そこから空になってしまう行数・列数を $R_x,C_x$ と決め打てば、除外すべき置き方はどの行・列を空にするかを含めて、以下のようになる。
これを $0 \le R_x \le R_b, 0 \le C_x \le C_b$（ただし $R_x=R_b$ かつ $C_x=C_b$ を除く）の範囲で全探索し、
${}_{R_b \times C_b}C_{B}$ から除外すれば、$f_b(R_b,C_b)$ が求められる。
これも $O(N^2M^2)$ で計算できる。
何の個数を $(-1)^k$ の $k$ とすればよいか少し迷うが、「必ず空行・空列にすると定める行数+列数」とできる。
空行があってもよい条件でそれぞれの場合を求め、
その上で $(N+M-R_b-C_b-R_w-C_w)$ の偶奇によって答えに足す正負を切り替えると、最終的な答えが求まる。
これなら前計算は必要なく、$R_b,C_b,R_w,C_w$ の総当たりのみで済む。
相変わらず、包除原理はなかなか直感的には見えづらい。
なんでこんな解かれてるの？
SegmentTreeなどでは解きづらい。
1種類の値 $x$ に限定すれば、SegmentTreeを使って区間 $[l,r]$ に含まれる $x$ の個数を取得し、
2で割って切り捨てることで $x$ で作れるペア数は $O(\log{N})$ でわかるが、
それを$A_i$ の値の種類数… $O(N)$ 回繰り返さなければならない。全部で $O(QN\log{N})$ で余裕のTLE。
1つの値を1bitで管理してXORでマージすれば、「ペアにできない $x$ が存在するかどうか」がわかり、 popcountして区間長から引くことでペア数もわかるが、それもbit長が $O(N)$ になり、XORの演算に時間がかかるため無理。
Mo's Algorithm、クエリ平方分割を使う。なんか名前だけ聞いたことあった。
以下のような場合に使える。
今回の場合、現在の区間内の各値の個数（の偶奇）を管理しておけば、以下の要領で区間を1つ伸縮したときの答えを更新できる。
何らかの順序でクエリを並べ替え、その順に区間を伸縮させて答えを求めていくことを考える。
例えば $r$ の昇順でクエリをソートし、この順に区間を伸縮させて答えを求めていくと、
右端の伸縮は最小限となるが、左端の伸縮で毎回 $O(N)$ かかってしまう場合がある。
1 |-| 2 |----------------| 3 |-| 4 |-------------------|
そこで、$l$ を、なんか適当なブロックサイズ $B$ でグループ分けする。
その中ごとに $r$ の昇順でクエリを処理すると、左端の伸縮も1クエリ当たり最大 $O(B)$ で収まる。
<-B-> 1 |-| 2 |---------| 3 |--------| 4 |-----------------|
分割した分、この処理をグループの個数 $\dfrac{N}{B}$ 回繰り返す必要があるが、
全体の計算量はこの和となるので、$B=\dfrac{N}{\sqrt{Q}}$ 程度に設定すれば $O(N\sqrt{Q})$ となる。
本問題の制約では最大 $10^8$ となるが、、、 まぁ $r$ を動かす範囲は右のグループほど狭まるなどの定数倍の削減があり、間に合う。