Description Input 大三角形的所有短边可以看成由(n+1)*n/2个单位三角形的边界组成。如下图的灰色三角形所示。其中第1排有1个灰色三角形，第2排有2个灰色三角形，……，第n排有n个灰色三角形。所以输入格式是这样规定的：输入第一行为正整数n，其中1<=n<=1000，表示大三角形每边的长度。接下来的n行，第i+1行有i组数，从左到右每组数描述一个三角形，每组数都有3个数，这3个数非0即1，表示对应的短边是否被删除，0表示已被删除，1表示未被删除，依次按照三角形的左、右、下边的顺序来描述。所以第i+1行有3i个数，每个数是0或1
Output 仅包含一个整数T，表示有多少个三角形的边界都没有被删除。
Sample Input
5
1 1 1
1 1 0 1 1 0
1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 1 1 0 1 1
Sample Output
19
统计有多少个三角形
枚举底边所在的直线
对于一个三角形，它的条件是底边是实线，左右两边要比底边长
我们先预处理出exl和exr，分别表示往左上最多延伸多长，往右上最多延伸多长
对于底边两点i和j，i<j
它需要满足的条件是（实线我们可以直接一段一段的处理）
j-i<=exr[i]，j-i<=exl[j]
所以j<=exr[i]+i，j-exl[j]<=i
然后我们先把j-exl[j]排一个序，从小到大枚举i，加入j-exl[j]<=i的点（即a[j]++），注意要把j<=i的减掉
a[i]数组用树状数组维护，再统计a数组中[1..exr[i]+i]的和就可以了
一开始不知道，所以我把每一个j看成一个平面上的点，坐标为（j,j-exl[j]），枚举i，统计横坐标小于等于exr[i]+i且纵坐标小于等于i的点
用二维树状数组维护这个和，然后过了
这里就只贴二维的那个了（第一种方法没有写）
const
maxn=;
var
tri:array[..maxn,..maxn,..]of integer;
exl,exr,c:array[..maxn,..maxn]of integer;
n,ans:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure init;
var
i,j:integer;
begin
read(n);
for i:= to n do
for j:= to i do
read(tri[i,j,],tri[i,j,],tri[i,j,]);
end; function lowbit(x:longint):longint;
begin
exit(x and -x);
end; procedure add(x,y,z:longint);
var
h:longint;
begin
while x<=n+ do
begin
h:=y;
while h<=n+ do
begin
inc(c[x,h],z);
h:=h+lowbit(h);
end;
x:=x+lowbit(x);
end;
end; function sum(x,y:longint):longint;
var
h:longint;
begin
sum:=;
while x> do
begin
h:=y;
while h> do
begin
inc(sum,c[x,h]);
h:=h-lowbit(h);
end;
x:=x-lowbit(x);
end;
end; procedure get;
var
h,l,r,i:longint;
begin
for h:= to n do
begin
l:=;
while l<=h do
begin
while (tri[h,l,]=)and(l<=h) do
inc(l);
if l>h then break;
r:=l+;
while tri[h,r,]= do
inc(r);
for i:=l to r do
add(i,max(,i-exl[h,i]),);
for i:=l to r do
begin
add(i,max(,i-exl[h,i]),-);
inc(ans,sum(min(n+,exr[h,i]+i),i));
end;
l:=r+;
end;
end;
end; procedure work;
var
i,j:longint;
begin
for i:= to n do
for j:= to i do
begin
if tri[i,j,]= then exr[i,j]:=exr[i-,j]+;
if tri[i,j,]= then exl[i,j+]:=exl[i-,j]+;
end;
get;
for i:= to n do
for j:= to i+ do
begin
exl[i,j]:=;
exr[i,j]:=;
end;
for i:=n downto do
for j:= to i do
begin
if tri[i,j,]= then exl[i-,j]:=exl[i,j]+;
if tri[i,j,]= then exr[i-,j]:=exr[i,j+]+;
end;
get;
write(ans);
end; begin
init;
work;
end.