Original proposer: admin

When only cloud \(k\) is removed, the answer can be found as the sum of:

1. the number of cells that are not covered by any cloud
2. the number of cells that are covered only by cloud \(k\)

To find these values, first compute for every cell \((r,c)\) how many clouds covers it.

To do so, it is sufficient to process the following kind of query \(N\) times:

• add \(1\) to the rectangular regions with the diagonal between \((u,l)\) and \((d,r)\).

In this problem, we are only interested in the results after processing all \(N\) queries, so we aim at processing all additions at once.

We will use a two-dimensional version of cumulative sum trick. (In Japanese community, this is called two-dimensional imos method.)

The specific procedure is as follows:

• Let \(A\) be the sought two-dimensional array, where each element can be accessed as \(A[i][j]\).
• First, initialize the elements of \(A\) with \(0\).
• Then, to perform “add \(1\) to the rectangular regions with the diagonal between \((u,l)\) and \((d,r)\),” perform the following four operations:
  • Add \(1\) to \(A[u][l]\).
  • Add \(-1\) to \(A[u][r+1]\).
  • Add \(-1\) to \(A[d+1][l]\).
  • Add \(1\) to \(A[d+1][r+1]\).
• After executing the process above for all addition queries, perform the following steps to obtain the final results:
  • Take the cumulative sums with respect to the second index of \(A\). In other words, add \(A[i][j]\) to \(A[i][j+1]\) in ascending order of \(j\).
  • Take the cumulative sums with respect to the first index of \(A\). In other words, add \(A[i][j]\) to \(A[i+1][j]\) in ascending order of \(i\).

In the end, the results of processing all addition queries can be computed in a total of \(O(HW+Q)\) time, when the dimensions of the array is \(H \times W\) and the number of addition queries is \(Q\).

Now we have found the number of cells that are not covered by any clouds.

All that left is to compute the number of cloud covered only by cloud \(k\).

Since we have identified the cells that are covered by exactly one cloud, it is sufficient to determine for each such cell which cloud covers it.

How can we achieve this?

Modify the addition query defined above into the following:

• for cloud \(k\), add \(k\) to the rectangular region covered by the cloud.

This way, we can identify, for each cell covered by exactly one cloud, which cloud covers that cell.

The answers can be found by appropriately processing these counts.
When the dimensions of the grid is \(H \times W\), the answer can be found in a total of \(O(HW+N)\) time.

Sample code (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;
}