Zobrist hashの考え方を応用した方法を解説します。 Zobrist hashについては、例えば下記の記事等を参照してください。

集合をハッシュする (Zobrist hashing)

\(1\) から \(10^{18}\) 程度のランダムな値を持つ長さ \(N\) の配列 \(P = (P_1, P_2, \dots, P_N)\) を用意します。\(2000 \times 2000\) の2次元配列 \(A\) を最初すべての要素を \(0\) で初期化し、\(i\) 番目のクエリで以下の処理を行うことを考えます。

• \((U_i,L_i),(D_i,R_i)\) を対角とした長方領域全体に \(P_i\) を xor する。

（実際にこの操作を愚直に行うとTLEします。高速化については最後に議論します。） このようにして得られた配列では、十分に高い確率で以下が成り立ちます。

• 配列の要素が \(0\) である場所では雲が1つも重なっていない。
• ある \(i\) が存在して配列の要素が \(P_i\) と一致するならば、その場所には雲 \(i\) が一つだけ重なっている。
• それ以外の値の場所では雲が2つ以上重なっている。

（これは、\(A\) の各要素の値が、そこに重なっているインデックスの集合の Zobrist hash であると考えると自然に従います。）

したがって、 \(P_1, P_2, \dots, P_N\) がどのインデックスに対応するかをハッシュテーブル等で管理して、以下のようにすれば答えを得ることができます。

• 変数 \(add\) を \(0\)、長さ \(N\) の配列 \(only\) のすべての要素を \(0\) で初期化する。
• \(A\) の各要素について以下を行う。
  • 値が \(0\) のとき、\(add\) に \(1\) を加える。
  • ある \(i\) が存在して配列の要素が \(P_i\) と一致するとき、\(only_i\) に \(1\) を加える。
  • 上記以外の場合は何もしない。
• すべての要素を見た後、\(i = 1,2,\dots,N\) について \(add + only_i\) の値が求める答えである。

最後に、長方形領域に \(P_i\) を行う操作の高速化について考えます。これは、2次元imos法の要領で以下のように行えばよいです。

• \(2001 \times 2001\) の2次元配列 \(A\) をすべての要素を \(0\) で初期化する。
• \(i = 1,2,\dots,N\) の順に以下を行う。
  • \(A[U_i][L_i]\) に \(P_i\) を xor する
  • \(A[U_i][R_i+1]\) に \(P_i\) を xor する
  • \(A[D_i+1][L_i]\) に \(P_i\) を xor する
  • \(A[D_i+1][R_i+1]\) に \(P_i\) を xor する
• \(r = 1.2,\dots,2001\) について \(A\) の \(r\) 行目の累積 xor をとる
• \(c = 1.2,\dots,2001\) について \(A\) の \(c\) 列目の累積 xor をとる