2445.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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("%d\n",ans);
}
int main()
{
	while(init())
	{
		doit();
	}
	return 0;
}