問題原案: admin

雲 \(k\) のみを取り除いた場合の答えは次の \(2\) つの和として求められます。

1. どの雲にも覆われていないマスの数
2. 雲 \(k\) のみに覆われているマスの数

これらを求めるため、まずは全てのマス \((r,c)\) についてそのマスを何個の雲が覆っているか求めてみましょう。

このためには、以下のクエリが \(N\) 個処理出来れば良いことになります。

• \((u,l),(d,r)\) を対角とした長方領域全体に \(1\) を加算する。

今回は、 \(N\) 個全てのクエリを処理した後の結果だけ分かれば良いことを利用して、全ての加算をまとめて高速に処理することを考えます。

このために、 二次元 imos 法 と呼ばれる方法を使うことが出来ます。

具体的な手順は次の通りです。

• 求める二次元配列を \(A\) とする。各要素には \(A[i][j]\) でアクセスできるものとする。
• 最初に、 \(A\) 中の要素を全て \(0\) で初期化する。
• 次に、「 \((u,l),(d,r)\) を対角とした長方領域全体に \(1\) を加算する。」を実現するため、以下の \(4\) つの操作を行う。
  • \(A[u][l]\) に \(1\) 加算する。
  • \(A[u][r+1]\) に \(-1\) 加算する。
  • \(A[d+1][l]\) に \(-1\) 加算する。
  • \(A[d+1][r+1]\) に \(1\) 加算する。
• 上記の処理を全ての加算クエリについて行った後、最終的な結果を得るために以下の処理を行う。
  • \(A\) の \(2\) 番目の添え字について累積和を取る。つまり、 \(A[i][j+1]\) に \(A[i][j]\) を加算することを \(j\) の昇順に行う。
  • \(A\) の \(1\) 番目の添え字について累積和を取る。つまり、 \(A[i+1][j]\) に \(A[i][j]\) を加算することを \(i\) の昇順に行う。

こうすると、配列の大きさを \(H \times W\) 、加算クエリの個数を \(Q\) とした際、全ての加算クエリを処理した後の結果を時間計算量 \(O(HW+Q)\) で得ることができます。

こうして、どの雲にも覆われていないマスの個数を求めることができました。

残るは特定の雲 \(k\) のみに覆われている雲のマスの個数を全ての雲について求めることです。

雲 \(1\) つのみに覆われているマスの個数は先ほどの手順で求められているので、そのマスを覆っているのがどの雲かを特定すればよいです。

さて、これを実現するためにはどうすれば良いでしょうか?

先程の加算クエリを以下の通りに読み替えればよいです。

• 雲 \(k\) について、その雲が覆う長方領域全体に \(k\) を加算する。

こうすると、雲 \(1\) つだけに覆われているマスがどの雲に覆われているかが分かります。

あとは、これらを適切に集計することで答えを求めることができます。
マス目の大きさを \(H \times W\) としたとき、全体で時間計算量 \(O(HW+N)\) で求められます。

実装例 (C++)

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  vector<vector<ll>> a(2025,vector<ll>(2025,0));
  vector<vector<ll>> b(2025,vector<ll>(2025,0));
  ll n;
  cin >> n;
  for(ll k=1;k<=n;k++){
    ll u,d,l,r;
    cin >> u >> d >> l >> r;
    d++; r++;
    a[u][l]++;
    a[u][r]--;
    a[d][l]--;
    a[d][r]++;
    b[u][l]+=k;
    b[u][r]-=k;
    b[d][l]-=k;
    b[d][r]+=k;
  }

  for(ll i=0;i<2025;i++){
    for(ll j=0;j<2025;j++){
      if(j){
        a[i][j]+=a[i][j-1];
        b[i][j]+=b[i][j-1];
      }
    }
  }
  for(ll i=0;i<2025;i++){
    for(ll j=0;j<2025;j++){
      if(i){
        a[i][j]+=a[i-1][j];
        b[i][j]+=b[i-1][j];
      }
    }
  }

  vector<ll> bk(n+1,0);
  for(ll i=1;i<=2000;i++){
    for(ll j=1;j<=2000;j++){
      if(a[i][j]==0){bk[0]++;}
      else if(a[i][j]==1){bk[b[i][j]]++;}
    }
  }
  for(ll i=1;i<=n;i++){
    cout << bk[0]+bk[i] << "\n";
  }
  return 0;
}