A. Grid L
まず，長方形を与えたときに L-shape を最大いくつとれるかを考えます．
L-shape は縦線と横線をひとつずつ使うので，縦線と横線の個数の $\min$ が上界です．実際にマッチングも作れます．
あとは，$p+2q$ が適切になるすべての $(n,m)$ を探索すればよいです．
B2. Unique Values (Hard version)
ある添え字集合 $I$ を質問したとします．返答と $|I|$ の差分から，出現頻度 $2, 3$ のいずれかであるようなものに対する出現頻度の和が手に入ります．
出現頻度 $3$ であるような種類は $0, 1$ のどちらかなので，偶奇を見ることで，出現頻度 $3$ のものがあるかが分かります．
$I$ を適当な列 $i_0,i_1,\ldots,i_{2N}$ の prefix として二分探索することで，この列の中で一番右側にある答のひとつを手に入れられます．これまで見つかった答を先頭に置いてこのような二分探索をやることで，未発見の答を手に入れられます．
C. Coloring a Red Black Tree
戦略としては，黒頂点の順列をとって手前から順に赤になるまで連打していくということになります．
もう少し考えると，隣接する黒頂点の順序だけしか答に影響しません．逆に隣接する黒頂点の順序を決めると，木なので toposort が存在し，そういう順列がとれます．
結局，黒頂点を含む辺を向きづけるという問題だと思えます．親辺の向き $2$ 種それぞれに対して，subtree 内で発生するコストの最小値を持つというタイプの木 DP で解けます．
D. MEX Replacement on Tree
操作が $1$ 回以下であることに注意．各頂点に対して，
- $A[v]$：現在の頂点が持つ値
- $B[v]$：現在の mex（$f(v)$）
- $C[v]$：現在の 2nd-mex
とします．
$v$ を変更したときには，$w\in \mathrm{subtree}(v)$ でのスコアだけが変更されます．$A[v]\neq B[v]$ であり，順列であることから subtree 内では必ず $A[v]$ が欠けた状態になります．
$a=A[v],b=B[v]$ として $w$ を部分木 $v$ に含まれる頂点とします．
- $a<b$ という変更：$w$ のスコアはもともと $b$ 以上．これがすべて $a$ に代わる．これはスコアが減るだけなので考えなくてよい．（なお計算も簡単）
- $a>b$ という変更：$w$ のスコアはもともと $b$ 以上．$B[w]=b$ ならば変更先は $\min(a, C[w])$．$b<B[w]$ ならば変更先は $\min(a,B[w])$．
スコアの変化がすべて式にできました．結局，$B[w]=b$ や $b<B[w]$ という制約下で，$\min(a, C[w])$ や $\min(a,B[w])$ の和がとれればよいということになります．
部分木は区間になおして，$b$ について降順に計算することにすると，$2$ 次元点群への追加削除と，矩形和の計算に帰着されます．例えば Wavelet Matrix で $O(N\log^2N)$ 時間です．
E. Weird Chessboard
とりあえず個数制約がない場合の解について考えます．
$(0,i)$ に 1 を書くと，$(0,i+1)$ で詰んだりします．それで
000000.
0......
0......
0......
0......
0......
.......まで確定します．同様にやっていくと左上半分が 0 で埋まったりします．
000000.
00000..
0000...
000....
00.....
0......
.......この時点で，反対角線上のマスは good になっています．あとは，「あるマスの左，上，左上が good ならば自身も good」というのが右下部分の全マスで成り立てば ok です．ここから $(i,j),(i-1,j),(i,j-1)$ の和が偶数というのが条件になることが分かります．
ここから，最下段を自由に埋めるごとに，解が一意にあることが分かります．また，$i=0,1,2,\ldots$ 順に $(n-1,i)$ を決めていくと，その時点で $(n-1-j,i+j)$ 部分が決まります．つまり，反対角方向について長い区間から順に決まっていくということになります．
あとは，ビームサーチすれば解が出てきます．これを高速化する必要があります．
$N$ で作った解の左下 $(N-1)\times (N-1)$ に制限したものがそのまま解になっていることがよくあります．（作った解における密度がだいたい一様だと思うとそういう推測にはなります．）これを使って $N$ で作った解を $N-1,N-2,\ldots,$ に当てはめられるかをチェックして，失敗する大きさがあれば解を再構築ということにします．
これで十分高速かつ，ソースコード埋め込みに耐えるだけの解を構築できました．
