@Rarfaeal
2019-12-12T04:34:54.000000Z
字数 2546
阅读 348
3 4
1 3 2 1
1 3 2 4
1 2 3 4
8
1 2 2 1
1 1 2 1
1 1 3 4
1 1 1 1
2 2 3 3
3 4 2 2
1 3 3 1
2 4 3 4
8
4
38
1
8
12
27
4
Uses math;
Const
question=1000000+10;
total=200+10;
var
sqrnum,bucket:array[-1..sqr(total)] of longint;
matrix:array[-1..total,-1..total] of longint;
point:array[-1..7,-1..question] of longint;
ans:array[-1..question] of longint;
i,j,m,a,b,c,d,n1,n2,sum,time,node_num:longint;
procedure Swap(var a,b:longint); var t:longint; begin t:=a; a:=b; b:=t; end;
function Gcd_(a,b:longint):longint;
var c:longint;
begin
c:=a mod b;
while c<>0 do begin a:=b; b:=c; c:=a mod b; end; exit(b);
end;
function Locate(node:longint):longint;
begin
if node mod node_num=0 then exit(node div node_num);
exit(node div node_num+1);
end;
procedure Sort(l,r:longint);
var i,j,k,s1,s2,s3,s4:longint;
begin
i:=l; j:=r; s1:=point[5,(l+r) >> 1]; s2:=point[2,(l+r) >> 1]; s3:=point[6,(l+r) >> 1]; s4:=point[4,(l+r) >> 1];
repeat
while (point[5,i]<s1)or((point[5,i]=s1)and(point[2,i]<s2))or((point[5,i]=s1)and(point[2,i]=s2)and(point[6,i]<s3))
or((point[5,i]=s1)and(point[2,i]=s2)and(point[6,i]=s3)and(point[4,i]<s4)) do inc(i);
while (point[5,j]>s1)or((point[5,j]=s1)and(point[2,j]>s2))or((point[5,j]=s1)and(point[2,j]=s2)and(point[6,j]>s3))
or((point[5,j]=s1)and(point[2,j]=s2)and(point[6,j]=s3)and(point[4,j]>s4)) do dec(j);
if i<=j then begin for k:=1 to 7 do Swap(point[k,i],point[k,j]); inc(i); dec(j); end;
until i>=j;
if i<r then Sort(i,r); if j>l then Sort(l,j);
end;
procedure Ready;
var i,j,k:longint;
begin
read(n1,n2); for i:=1 to n1 do for j:=1 to n2 do read(matrix[i,j]);
read(m); node_num:=trunc(max(n1,n2)/sqrt(sqrt(m)));
for i:=1 to sqr(total) do sqrnum[i]:=sqr(i);
for i:=1 to m do
begin
point[7,i]:=i; for j:=1 to 4 do read(point[j,i]);
point[5,i]:=Locate(point[1,i]); point[6,i]:=Locate(point[3,i]);
end;
Sort(1,m); a:=1; b:=1; c:=1; d:=1; sum:=1; bucket[matrix[1,1]]:=1;
end;
procedure Transefer(key,l,r,mode:longint);
var i:longint;
begin
if mode=1 then for i:=l to r do
begin
dec(sum,sqrnum[bucket[matrix[key,i]]]);
inc(bucket[matrix[key,i]]);
inc(sum,sqrnum[bucket[matrix[key,i]]]);
end;
if mode=2 then for i:=l to r do
begin
dec(sum,sqrnum[bucket[matrix[i,key]]]);
dec(bucket[matrix[i,key]]);
inc(sum,sqrnum[bucket[matrix[i,key]]]);
end;
end;
begin
Ready;
for i:=1 to m do
begin
while (a>point[1,i]) do begin dec(a); Transefer(a,b,d,1); end;
while (c>point[3,i]) do begin Transefer(c,b,d,2); dec(c); end;
while (c<point[3,i]) do begin inc(c); Transefer(c,b,d,1); end;
while (a<point[1,i]) do begin Transefer(a,b,d,2); inc(a); end;
while (b>point[2,i]) do begin dec(b); Transefer(b,a,c,1); end;
while (d>point[4,i]) do begin Transefer(d,a,c,2); dec(d); end;
while (d<point[4,i]) do begin inc(d); Transefer(d,a,c,1); end;
while (b<point[2,i]) do begin Transefer(b,a,c,2); inc(b); end;
ans[point[7,i]]:=sum;
end;
for i:=1 to m do writeln(ans[i]);
writeln(time);
end.