题解 SP16180 【RATAR - Ratar】
hicc0305
2018-10-04 15:15:58
枚举两个矩形的连接点，然后统计出左上的所有矩形的面积，用f[i]存面积为i的矩形有多少个。然后统计右下的所有矩形的面积的时候，每算出一个矩形面积j，答案就加上f[j]。然后左下和右上同理。
注意：清空时千万不要用memset，会超时的，然后我一开始是用map的，因为STL的劣根性，会T。。是的不管是用clear()还是一个一个删都会T的！但理论时间复杂度上$n^4*log_2n$是过得去的！！
那么代码：
```
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma GCC optimize (2)
#define int long long
#define it int
using namespace std;
const int Max=2500*1000;
inline int read()
{
int X=0,w=0; char c=0;
while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
return w?-X:X;
}
int n,ans=0;
int a[60][60],b[60][60];
int sum[60][60];
it f[Max*2];
int get(int x1,int y1,int x2,int y2)
{
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=b[i][j-1]+a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
sum[i][j]=sum[i-1][j]+b[i][j];
for(int a=1;a<=n;a++)
for(int b=1;b<=n;b++)
{
for(int c=a+1;c<=n;c++)
for(int d=b+1;d<=n;d++)
f[get(a+1,b+1,c,d)+Max]++;
for(int c=1;c<=a;c++)
for(int d=1;d<=b;d++)
ans+=f[get(a,b,c,d)+Max];
for(int c=a+1;c<=n;c++)
for(int d=b+1;d<=n;d++)
f[get(a+1,b+1,c,d)+Max]--;
for(int c=1;c<=a;c++)
for(int d=b+1;d<=n;d++)
f[get(a,b+1,c,d)+Max]++;
for(int c=a+1;c<=n;c++)
for(int d=1;d<=b;d++)
ans+=f[get(a+1,b,c,d)+Max];
for(int c=1;c<=a;c++)
for(int d=b+1;d<=n;d++)
f[get(a,b+1,c,d)+Max]--;
}
printf("%lld",ans);
return 0;
}
```