program exam;
var sum,map:array[0..1001,0..2001] of longint;
spot:array[0..1000001] of int64;
g:array[0..1001,0..1001] of char;
n,m,t,r,i,j,tot,vi,vj:longint;ans:int64;
procedure initfile;
begin
assign(input,'b.in');
reset(input);
assign(output,'b.out');
rewrite(output);
end;
procedure closefile;
begin
close(input);
close(output);
end;
procedure qs(l,r:longint);
var i,j:longint;x,tmp:int64;
begin
i:=l;j:=r;
x:=spot[(i+j) shr 1];
repeat
while spot[i]>x do inc(i);
while spot[j]<x do dec(j);
if i<=j then
begin
tmp:=spot[i];spot[i]:=spot[j];spot[j]:=tmp;
inc(i);dec(j);
end;
until i>j;
if i<r then qs(i,r);
if l<j then qs(l,j);
end;
function min(x,y:longint):longint;
begin if x<y then exit(x) else exit(y);end;
function max(x,y:longint):longint;
begin if x>y then exit(x) else exit(y);end;
procedure initdata;
var i,j,k,h:longint;
begin
readln(n,m,t,r);
fillchar(sum,sizeof(sum),0);
for i:=1 to n do
begin
for j:=1 to m do
begin
vi:=i-j+m;vj:=i+j-1;
read(g[i,j]);
if g[i,j]='O' then
map[vi,vj]:=1;
end;
readln;
end;
for i:=1 to n+m-1 do
for j:=1 to n+m-1 do
begin
sum[i,j]:=sum[i-1,j]+sum[i,j-1]-sum[i-1,j-1]+map[i,j];
end;
for i:=1 to n do
for j:=1 to m do
if g[i,j]='*' then
begin
inc(tot);
vi:=i-j+m;vj:=i+j-1;

spot[tot]:=sum[min(vi+r,n+m-1),min(vj+r,n+m-1)]-
sum[min(vi+r,n+m-1),max(vj-r,1)-1]-
sum[max(vi-r,1)-1,min(vj+r,n+m-1)]+
sum[max(vi-r,1)-1,max(vj-r,1)-1];

end;
qs(1,tot);
end;
begin

initdata;
ans:=0;
for i:=1 to t do
begin
ans:=ans+spot[i];
end;
writeln(ans);

end.

（语文超渣求轻喷………………T_T

我们发现，一个塔的攻击范围是一个斜着的正方形。
换句话说，我们考虑左右对角线，我们依照这两种对角线把每个点重新标号为。 (i', j') 表示一个坐标为 (i, j) 的点在第 i' 条左对角线，在第 j' 条右对角线上。
看过八皇后问题后就会明白了。
那么标号方法就是，对于一个原坐标为 (i, j) 的点： i' = i-j+m, j' = i+j-1 (1 <= i <= n, 1 <= j <= m) 。
一个塔在新坐标 (x', y') 能够攻击的到新坐标 (i', j') 满足以下条件的所有点： max(x'-R, 1) <= i' <= min(x'+R, n), max(y'-R, 1) <= j' <= min(y'+R, m)

这个可以用二维前缀和轻松地算出。
（二维前缀和：sum[i][j]表示矩阵A[n][m]的子矩阵A[1...i][1...j]的和，递推式sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j]
询问A[x0...x1][y0...y1]的和就是sum[x1][y1]-sum[x0-1][y1]-sum[x1][y0-1]+sum[x0-1][y0-1]）
时间复杂度 O(nm) 。

Falsyta