题解 - Vijos

2

yxuanw_keith LV 7 @ 2014-07-20 09:48:27

树状数组维护，加枚举顶点

const maxn=1002;
type point=^node;
node=record
x:longint;
next:point;
end;
var i,j,nn,x,y,sum,k:longint;
c:char;
next:array[0..maxn] of point;
s,n,w,e:array[0..maxn,0..maxn] of longint;
t:array[1..maxn] of longint;
m,ans:array[0..maxn,0..maxn,0..1] of boolean;
p:point;
procedure add(x,sum:longint);
begin
while (x<=nn) do
begin
t[x]:=t[x]+sum;
x:=x+x and -x;
end;
end;
function find(x:longint):longint;
var s:longint;
begin
s:=0;
while (x>0) do
begin
s:=s+t[x];
x:=x-x and -x;
end;
exit(s);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
readln(nn);
for i:=1 to nn+1 do
begin
for j:=1 to 2*nn+1 do
begin
read(c);
case c of
'_':m[i,j div 2,0]:=true;
'|':m[i-1,(j+1) div 2,1]:=true;
end;
end;
readln;
end;
for i:=1 to nn+1 do
for j:=1 to nn+1 do
begin
if m[i,j-1,0] then e[i,j]:=e[i,j-1]+1;
if m[i-1,j,1] then n[i,j]:=n[i-1,j]+1;
end;
for i:=nn+1 downto 1 do
for j:=nn+1 downto 1 do
begin
if m[i,j,0] then w[i,j]:=w[i,j+1]+1;
if m[i,j,1] then s[i,j]:=s[i+1,j]+1;
end;
inc(nn);
for i:=1 to nn*2 do
begin
if i<=nn then
begin
x:=1; y:=i;
end else
begin
x:=i-nn; y:=nn;
end;
fillchar(next,sizeof(next),0);
fillchar(t,sizeof(t),0);
while (x<=nn) and (y>=1) do
begin
p:=next[x];
while (p<>nil) do
begin
add(p^.x,-1);
p:=p^.next;
end;
if w[x,y]>n[x,y] then
begin
if (find(x-n[x,y]-1)-find(x-min(w[x,y],n[x,y]+1+n[x-n[x,y]-1,y])-1))>0 then
ans[x-n[x,y]-1,y,1]:=true else
end;
if w[x,y]<n[x,y] then
begin
if (find(x-w[x,y]-1)-find(x-min(w[x,y]+1+w[x,y+w[x,y]+1],n[x,y])-1))>0 then
ans[x,y+w[x,y],0]:=true;
end;
add(x,1);
new(p);
k:=x+min(s[x,y],e[x,y])+1;
p^.x:=x; p^.next:=next[k];
next[k]:=p;
inc(x); dec(y);
end;
if i<=nn then
begin
x:=i; y:=1;
end else
begin
x:=nn; y:=i-nn+1;
end;
fillchar(next,sizeof(next),0);
fillchar(t,sizeof(t),0);
while (x>=1) and (y<=nn) do
begin
p:=next[x];
while (p<>nil) do
begin
add(p^.x,-1);
p:=p^.next;
end;
if e[x,y]<s[x,y] then
begin
if find(x+min(s[x,y],e[x,y]+1+e[x,y-e[x,y]-1]))-find(x+e[x,y])>0 then
ans[x,y-e[x,y]-1,0]:=true;
end else if e[x,y]>s[x,y] then
begin
if find(x+min(s[x,y]+1+s[x+s[x,y]+1,y],e[x,y]))-find(x+s[x,y])>0 then
ans[x+s[x,y],y,1]:=true;
end;
add(x,1);
k:=x-min(n[x,y],w[x,y])-1;
new(p);
p^.x:=x; p^.next:=next[k];
next[k]:=p;
dec(x); inc(y);
end;
end;
sum:=0;
for i:=1 to nn do
for j:=1 to nn do
begin
if ans[i,j][0] then inc(sum);
if ans[i,j][1] then inc(sum);
end;
writeln(sum);
end.

0

cenbinbin LV 9 @ 2015-06-30 10:54:06

const maxn=1002;
type point=^node;
node=record
x:longint;
next:point;
end;
var i,j,nn,x,y,sum,k:longint;
c:char;
next:array[0..maxn] of point;
s,n,w,e:array[0..maxn,0..maxn] of longint;
t:array[1..maxn] of longint;
m,ans:array[0..maxn,0..maxn,0..1] of boolean;
p:point;
procedure add(x,sum:longint);
begin
while (x<=nn) do
begin
t[x]:=t[x]+sum;
x:=x+x and -x;
end;
end;
function find(x:longint):longint;
var s:longint;
begin
s:=0;
while (x>0) do
begin
s:=s+t[x];
x:=x-x and -x;
end;
exit(s);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
readln(nn);
for i:=1 to nn+1 do
begin
for j:=1 to 2*nn+1 do
begin
read(c);
case c of
'_':m[i,j div 2,0]:=true;
'|':m[i-1,(j+1) div 2,1]:=true;
end;
end;
readln;
end;
for i:=1 to nn+1 do
for j:=1 to nn+1 do
begin
if m[i,j-1,0] then e[i,j]:=e[i,j-1]+1;
if m[i-1,j,1] then n[i,j]:=n[i-1,j]+1;
end;
for i:=nn+1 downto 1 do
for j:=nn+1 downto 1 do
begin
if m[i,j,0] then w[i,j]:=w[i,j+1]+1;
if m[i,j,1] then s[i,j]:=s[i+1,j]+1;
end;
inc(nn);
for i:=1 to nn*2 do
begin
if i<=nn then
begin
x:=1; y:=i;
end else
begin
x:=i-nn; y:=nn;
end;
fillchar(next,sizeof(next),0);
fillchar(t,sizeof(t),0);
while (x<=nn) and (y>=1) do
begin
p:=next[x];
while (p<>nil) do
begin
add(p^.x,-1);
p:=p^.next;
end;
if w[x,y]>n[x,y] then
begin
if (find(x-n[x,y]-1)-find(x-min(w[x,y],n[x,y]+1+n[x-n[x,y]-1,y])-1))>0 then
ans[x-n[x,y]-1,y,1]:=true else
end;
if w[x,y]<n[x,y] then
begin
if (find(x-w[x,y]-1)-find(x-min(w[x,y]+1+w[x,y+w[x,y]+1],n[x,y])-1))>0 then
ans[x,y+w[x,y],0]:=true;
end;
add(x,1);
new(p);
k:=x+min(s[x,y],e[x,y])+1;
p^.x:=x; p^.next:=next[k];
next[k]:=p;
inc(x); dec(y);
end;
if i<=nn then
begin
x:=i; y:=1;
end else
begin
x:=nn; y:=i-nn+1;
end;
fillchar(next,sizeof(next),0);
fillchar(t,sizeof(t),0);
while (x>=1) and (y<=nn) do
begin
p:=next[x];
while (p<>nil) do
begin
add(p^.x,-1);
p:=p^.next;
end;
if e[x,y]<s[x,y] then
begin
if find(x+min(s[x,y],e[x,y]+1+e[x,y-e[x,y]-1]))-find(x+e[x,y])>0 then
ans[x,y-e[x,y]-1,0]:=true;
end else if e[x,y]>s[x,y] then
begin
if find(x+min(s[x,y]+1+s[x+s[x,y]+1,y],e[x,y]))-find(x+s[x,y])>0 then
ans[x+s[x,y],y,1]:=true;
end;
add(x,1);
k:=x-min(n[x,y],w[x,y])-1;
new(p);
p^.x:=x; p^.next:=next[k];
next[k]:=p;
dec(x); inc(y);
end;
end;
sum:=0;
for i:=1 to nn do
for j:=1 to nn do
begin
if ans[i,j][0] then inc(sum);
if ans[i,j][1] then inc(sum);
end;
writeln(sum);
end.

0

yxuanw_keith LV 7 @ 2014-07-20 09:48:39

const maxn=1002;
type point=^node;
node=record
x:longint;
next:point;
end;
var i,j,nn,x,y,sum,k:longint;
c:char;
next:array[0..maxn] of point;
s,n,w,e:array[0..maxn,0..maxn] of longint;
t:array[1..maxn] of longint;
m,ans:array[0..maxn,0..maxn,0..1] of boolean;
p:point;
procedure add(x,sum:longint);
begin
while (x<=nn) do
begin
t[x]:=t[x]+sum;
x:=x+x and -x;
end;
end;
function find(x:longint):longint;
var s:longint;
begin
s:=0;
while (x>0) do
begin
s:=s+t[x];
x:=x-x and -x;
end;
exit(s);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
assign(input,'temp.in');reset(input);
readln(nn);
for i:=1 to nn+1 do
begin
for j:=1 to 2*nn+1 do
begin
read(c);
case c of
'_':m[i,j div 2,0]:=true;
'|':m[i-1,(j+1) div 2,1]:=true;
end;
end;
readln;
end;
for i:=1 to nn+1 do
for j:=1 to nn+1 do
begin
if m[i,j-1,0] then e[i,j]:=e[i,j-1]+1;
if m[i-1,j,1] then n[i,j]:=n[i-1,j]+1;
end;
for i:=nn+1 downto 1 do
for j:=nn+1 downto 1 do
begin
if m[i,j,0] then w[i,j]:=w[i,j+1]+1;
if m[i,j,1] then s[i,j]:=s[i+1,j]+1;
end;
inc(nn);
for i:=1 to nn*2 do
begin
if i<=nn then
begin
x:=1; y:=i;
end else
begin
x:=i-nn; y:=nn;
end;
fillchar(next,sizeof(next),0);
fillchar(t,sizeof(t),0);
while (x<=nn) and (y>=1) do
begin
p:=next[x];
while (p<>nil) do
begin
add(p^.x,-1);
p:=p^.next;
end;
if w[x,y]>n[x,y] then
begin
if (find(x-n[x,y]-1)-find(x-min(w[x,y],n[x,y]+1+n[x-n[x,y]-1,y])-1))>0 then
ans[x-n[x,y]-1,y,1]:=true else
end;
if w[x,y]<n[x,y] then
begin
if (find(x-w[x,y]-1)-find(x-min(w[x,y]+1+w[x,y+w[x,y]+1],n[x,y])-1))>0 then
ans[x,y+w[x,y],0]:=true;
end;
add(x,1);
new(p);
k:=x+min(s[x,y],e[x,y])+1;
p^.x:=x; p^.next:=next[k];
next[k]:=p;
inc(x); dec(y);
end;
if i<=nn then
begin
x:=i; y:=1;
end else
begin
x:=nn; y:=i-nn+1;
end;
fillchar(next,sizeof(next),0);
fillchar(t,sizeof(t),0);
while (x>=1) and (y<=nn) do
begin
p:=next[x];
while (p<>nil) do
begin
add(p^.x,-1);
p:=p^.next;
end;
if e[x,y]<s[x,y] then
begin
if find(x+min(s[x,y],e[x,y]+1+e[x,y-e[x,y]-1]))-find(x+e[x,y])>0 then
ans[x,y-e[x,y]-1,0]:=true;
end else if e[x,y]>s[x,y] then
begin
if find(x+min(s[x,y]+1+s[x+s[x,y]+1,y],e[x,y]))-find(x+s[x,y])>0 then
ans[x+s[x,y],y,1]:=true;
end;
add(x,1);
k:=x-min(n[x,y],w[x,y])-1;
new(p);
p^.x:=x; p^.next:=next[k];
next[k]:=p;
dec(x); inc(y);
end;
end;
sum:=0;
for i:=1 to nn do
for j:=1 to nn do
begin
if ans[i,j][0] then inc(sum);
if ans[i,j][1] then inc(sum);
end;
writeln(sum);
close(input);
end.