G - Scalene Triangle Area Editorial by physics0523
例えば \(K=5\) である場合、一番左上にあるコマは以下の 1
の部分を守ることになります。
11111111110
11111111000
11111100000
11110000000
11000000000
00000000000
基本的な方針は imos法 です。
最終的に左から右へと累積和をとることにすると、以下の +
の位置に \(+1\) 、 -
の位置に \(-1\) を置ければよいことになります。
(この累積和をとる動作を (1) とします (実装例 res
に対応します))
+.........-
+.......-..
+.....-....
+...-......
+.-........
...........
これを +
と -
に分けて取り扱うことを考えます。
+
について
上から下に累積和を取ることにすると、以下の +
に \(+1\) 、 -
に \(-1\) を置くことにすると、上から下に累積和を取った後に (1) において +
を置きたい位置に \(+1\) が置かれることになります。
(この累積和をとる動作を (2) とします (実装例 vert
に対応します))
+..........
...........
...........
...........
...........
-..........
-
について
こちらは少し工夫が必要です。累積和を以下のように取ることを考えます。
\(Sum[i][j] = Sum[i][j] + Sum[i-1][j+2]\)
このようにすると、斜め方向に累積和を取ることができます。
以下の -
に \(-1\) 、 +
に \(+1\) を置くことにすると、斜め方向に累積和を取った後に (1) において -
を置きたい位置に \(-1\) が置かれることになります。
(この累積和をとる動作を (3) とします (実装例 diag
に対応します))
..........-
...........
...........
...........
...........
+..........
各マスについて +
と -
を配置した後 (2)(3) の累積和をとると、 (1) の累積和をとる前の配列がどうあるべきかが分かります。その後 (1) の累積和をとると全てのマスについてそのマスを守っているコマの数がいくつかが得られるので、あとはクエリごとに答えていけばよいです。
計算量は時間 \(O(N^2+Q)\) 、空間 \(O(N^2)\) です。
各段階について +
や -
を置く位置が盤外になる可能性もあるので、配列を十分大きく確保する必要がある点に注意してください。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> vert(2022,vector<int>(11111,0));
vector<vector<int>> diag(2022,vector<int>(11111,0));
for(int i=0;i<n;i++){
string s;
cin >> s;
for(int j=0;j<n;j++){
if(s[j]=='O'){
vert[i][j]++;
if((i+m)<2022){vert[i+m][j]--;}
diag[i][j+2*m]--;
if((i+m)<2022){diag[i+m][j]++;}
}
}
}
vector<vector<int>> res(2022,vector<int>(11111,0));
for(int i=1;i<2022;i++){
for(int j=0;j<11111;j++){
vert[i][j]+=vert[i-1][j];
if((j+2)<11111){diag[i][j]+=diag[i-1][j+2];}
}
}
for(int i=0;i<2022;i++){
for(int j=0;j<11111;j++){
res[i][j]=diag[i][j]+vert[i][j];
}
}
for(int i=0;i<2022;i++){
for(int j=1;j<11111;j++){res[i][j]+=res[i][j-1];}
}
int q;
cin >> q;
while(q>0){
q--;
int x,y;
cin >> x >> y;
x--;y--;
cout << res[x][y] << '\n';
}
return 0;
}
posted:
last update: