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，表示有多少个三角形的边界都没有被删除。
预处理每个点向右上、左下、右、左四个方向延伸的最大长度，枚举左上-右下方向的路径，计算一边在这条路径上的三角形个数，可以排序并用树状数组维护
#include<cstdio> #include<algorithm> char buf[1000000],*ptr=buf,*pmx=buf+1000000; inline int g(){ if(ptr==pmx)fread(ptr=buf,1,1000000,stdin); return *(ptr++); } int _(){ int x=0,c=g(); while(c<48)c=g(); while(c>47)x=x*10+c-48,c=g(); return x; } const int N=1107; int n; int d1[N][N],d2[N][N],d3[N][N],v1[N][N],v2[N][N],v3[N][N],v4[N][N],xs[N],xs2[N],bit[N],tk[N],T=0,ans=0; struct itv{int l,r;}is[N],is2[N]; bool operator<(const itv&a,const itv&b){return a.l<b.l;} void inc(int w){ for(++w;w<N;w+=w&-w){ if(tk[w]!=T)tk[w]=T,bit[w]=0; ++bit[w]; } } int sum(int w){ int s=0; for(++w;w;w-=w&-w){ if(tk[w]!=T)tk[w]=T,bit[w]=0; s+=bit[w]; } return s; } int main(){ n=_(); for(int i=1;i<=n;++i){ for(int j=1;j<=i;++j){ d1[i][j]=_(); d3[i][j]=_(); d2[i+1][j]=_(); } } ++n; for(int i=1;i<=n;++i){ for(int j=1;j<=i;++j){ if(d2[i][j-1])v2[i][j]=v2[i][j-1]+1; if(d1[i-1][j])v4[i][j]=v4[i-1][j]+1; } for(int j=i;j;--j)if(d2[i][j])v3[i][j]=v3[i][j+1]+1; } for(int i=n;i;--i){ for(int j=1;j<=i;++j)if(d1[i][j])v1[i][j]=v1[i+1][j]+1; } for(int i=1;i<=n;++i){ for(int x=i,y=1,p;y<=n;){ while(!d3[x][y]&&y<=n)++x,++y; if(y>n)break; for(p=1;;++x,++y,++p){ xs[p]=v1[x][y]; is[p]=(itv){p-v2[x][y],p}; xs2[p]=v3[x][y]; is2[p]=(itv){p-v4[x][y],p}; if(!d3[x][y])break; } std::sort(is+1,is+p+1); ++T; for(int w=1,r=1;w<=p;++w){ while(r<=p&&is[r].l<=w)inc(is[r++].r); ans+=sum(w+xs[w])-sum(w); } std::sort(is2+1,is2+p+1); ++T; for(int w=1,r=1;w<=p;++w){ while(r<=p&&is2[r].l<=w)inc(is2[r++].r); ans+=sum(w+xs2[w])-sum(w); } } } printf("%d",ans); return 0; }