首先能够构成正方形的两个对顶点肯定在同一条对角线上，可以想到依次处理每条对角线上的点。

　　对于每个点，预处理出它能到的四个方向的连续1最多有多少个，记为p_up,p_down,p_left,p_right，显然，决定某一个点向右下能延伸的多少只取决于p_down和p_right中的较小值，决定某一个点向左上能延伸到多少只取决于p_up和p_left的较小值。

　　

　　对于每个点，记录它能到达的最右的x轴的绝对坐标，并记录它自身的y坐标。

　　统计一个点和它左上的点(在对角线上)能组成多少个正方形时，只要判断有多少个点向右能和它相交即可。比如统计5，只要记录1~4中有多少点向右能和红线交叉，显然5可以和1，3，4组成边上全部为1的正方形。

　　HDU给的题解没太看懂，我是用一个堆维护每个点能到的最右的x轴坐标，当堆顶元素向右不能到达该点的x坐标时，就可以将这个点删除，因为这个点已经没有用了，比如统计5时，就可以将2这个点删除，它已经不能和5以及以后的点组成正方形，然后再统计红线范围内有多少点即可，这里用树状数组线段树什么的都可以。

　　另外这题如果不一条条对角线分别统计会MLE。。。可能是以为我用了堆的缘故吧。。

　

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAXN 1005 5 using namespace std; 6 typedef pair
        
          pii; 7 typedef __int64 LL; 8 int cas,n,mz[MAXN][MAXN],d[MAXN][MAXN][4]; 9 int c[MAXN];10 int lowbit(int x){
   return x&-x;}11 void update(int k,int d){12     while(k
         
           1:right<- 2:top 3:bottom30         for(int i=1;i<=n;i++)31             for(int j=1;j<=n;j++)32                 d[i][j][0]=mz[i][j]?d[i][j-1][0]+1:0,33                 d[i][j][2]=mz[i][j]?d[i-1][j][2]+1:0;34         for(int i=n;i>=1;i--)35             for(int j=n;j>=1;j--)36                 d[i][j][1]=mz[i][j]?d[i][j+1][1]+1:0,37                 d[i][j][3]=mz[i][j]?d[i+1][j][3]+1:0;38         LL ans=0;39         //枚举对角线,能构成正方形的点的对顶点必然在一条对角线上40         for(int dt=-n+1;dt<=n-1;dt++){41             //用堆维护该对角线上向左和向右都能延伸到当前点的集合42             //并用树状数组统计某个区间内能到达该点的点的数量43             priority_queue
          
           
            ,greater
            
              > q;44 memset(c,0,sizeof c);45 for(int i=1-dt>0?1-dt:1;i<=n&&i+dt<=n;i++){46 int j=i+dt;47 if(mz[i][j]==0)continue;48 if(d[i][j][3]