http://poj.org/problem?id=2445
#include"stdio.h"
#include"algorithm"
using namespace std;
int l[1500][1500],r[1500][1500],u[1500][1500],d[1500][1500],lu[1500][1500],rd[1500][1500];
int n;
inline int max(int a,int b)
{
return a>b?a:b;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
bool init()
{
int i,j,m,k,a,b;
char c;
if(scanf("%d",&n)!=1)
return 0;
scanf("%d",&m);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
r[i][j]=d[i][j]=0;
while(m--)
{
getchar();
scanf("%c%d%d%d",&c,&i,&j,&k);
i--,j--;
if(c=='H')
{
r[i][j]=max(r[i][j],k);
}
else
{
d[i][j]=max(d[i][j],k);
}
}
for(i=0;i<n;i++)
{
a=0,b=0;
for(j=0;j<n;j++)
{
if(j>b)b=r[i][j]+j,a=j;
else if(r[i][j]+j>b)b=r[i][j]+j;
l[i][j]=a;
}
a=n-1,b=n-1;
for(j=n-1;j>=0;j--)
{
if(j<b)b=l[i][j],a=j;
else if(l[i][j]<b)b=l[i][j];
r[i][j]=a;
}
}
for(j=0;j<n;j++)
{
a=0,b=0;
for(i=0;i<n;i++)
{
if(i>b)b=d[i][j]+i,a=i;
else if(d[i][j]+i>b)b=d[i][j]+i;
u[i][j]=a;
}
a=n-1,b=n-1;
for(i=n-1;i>=0;i--)
{
if(i<b)b=u[i][j],a=i;
else if(u[i][j]<b)b=u[i][j];
d[i][j]=a;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
lu[i][j]=min(j-l[i][j],i-u[i][j]);
rd[i][j]=min(r[i][j]-j,d[i][j]-i);
}
}
return 1;
}
int m,c[1500],id[1500],x[1500],y[1500];
inline int lowbit(int x)
{
return x&(x^(x-1));
}
bool cmp(int a,int b)
{
return rd[x[a]][y[a]]+a<rd[x[b]][y[b]]+b;
}
int count(int bx,int by)
{
int i,j,k,ans=0;
m=min(n-bx,n-by);
for(i=0;i<m;i++)
id[i]=i,x[i]=bx+i,y[i]=by+i,c[i]=0;
sort(id,id+m,cmp);
for(i=0,j=0;i<m;i++)
{
k=i+1;
while(k)
{
ans+=c[k];
k-=lowbit(k);
}
k=i-lu[bx+i][by+i]/*-1+1*/;
while(k)
{
ans-=c[k];
k-=lowbit(k);
}
k=i+1;
while(k<=m)
{
c[k]++;
k+=lowbit(k);
}
while(j<m&&(id[j]+rd[x[id[j]]][y[id[j]]])<=i)
{
k=id[j++]+1;
while(k<=m)
{
c[k]--;
k+=lowbit(k);
}
}
}
return ans;
}
void doit()
{
int x,y,ans=0;
for(x=0;x<n;x++)
ans+=count(x,0);
for(y=1;y<n;y++)
ans+=count(0,y);
printf("%dn",ans);
}
int main()
{
while(init())
{
doit();
}
return 0;
}