【PGBATTLE2019_かつおぶし3】聴取

[Q] https://products.sint.co.jp/q_list

マンハッタン距離をそのまま扱うと、

4 3 2 3 4
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4

となって、二次元座標としては扱いにくい。
座標を45度回転させることで、縮尺はルート2倍されるが

2   2   2
　1   1  
2   0   2
　1   1
2   2   2

マンハッタン距離なので埋めてよくて
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2

管理を変えられる。

Q. 座標の回転？
A. (x, y) = (x-y, x+y)
にするのが一般的かも。この回転で、原点を中心に-45度回る。縮尺はルート2倍に大きくなるけど、マンハッタン距離で計算する世界なので、x+yは変わらない。
1,1の点が0,2に動く。

これに従って、
x+y は 0~6000,
x-y は -3000 ~ 3000
まで取りうるので、x-yには+3005 の補正をするといい。

DP[6010][6010] = 要素の有無 でデータ管理。
二次元累積和をして、
DP[6010][6010] = 自分含め左上の要素の総数 で管理される

Q. 二次元累積和？
A. 4点の足し引きで、範囲の要素数を導けます。

0 0 0 0 0 0
0<0>0 1<1>1
0 0 0 1 1 1
0 0 0 2 2 2 
0<0>0 2<3>3
0 0 0 2 3 3

DP[4][4] - DP[1][4] - DP[4][1] + DP[1][1]
3 - 1 - 0 + 1
をすることで、
(2,2) ~ (4,4)の要素数の総和が得られる。

実装。

ll DP[6010][6010];
ll X[300010];
ll Y[300010];
ll D[300010];
ll A[300010];
ll B[300010];
int main(){
 cincout();
 
 // かいてん
 // x-y, x+yにする
 // x = -3000 ~ 3000
 // y = 0 ~ 6000
 
 // x座標は+3000の補正
 ll N;
 cin >> N;
 rep(i, N) cin >> X[i] >> Y[i] >> D[i];
 rep(i, N){
   A[i] = X[i] - Y[i] + 3000;
   B[i] = X[i] + Y[i];
   ++DP[B[i]][A[i]]; // いもす
 }
 rep(i, 6001){
   ll t=0;
   rep(j, 6001){
     t += DP[i][j];
     DP[i][j] = t;
   }
 }

 rep(j, 6001){
   ll t=0;
   rep(i, 6001){
     t += DP[i][j];
     DP[i][j] = t;
   }
 }

 rep(i, N){
   ll ans = 0;
   ll a=A[i], b=B[i], d=D[i];
   ans += DP[min(6000, b+d)][min(6000, a+d)];
   if (b-d>0) ans -= DP[b-d-1][min(6000, a+d)];
   if (a-d>0) ans -= DP[min(6000, b+d)][a-d-1];
   if (b-d>0 && a-d>0) ans += DP[b-d-1][a-d-1];
   cout << ans << endl;
 }
}