记录编号	409900	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]双十字	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.321 s
提交时间	2017-05-29 20:32:16	内存使用	61.34 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e6+10,p=1000000009;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int c2(int x){return ((ll)x*(x-1)>>1)%p;}
struct bit{
	int a[N];
	void add(int p,int d){
		for (p++;p<N;p+=p&-p) a[p]=inc(a[p],d);
	}
	int sum(int p){
		int ans=0;
		for (p++;p>0;p-=p&-p) ans=inc(ans,a[p]);
		return ans;
	}
	int sum(int l,int r){
		return dec(sum(r),sum(l-1));
	}
}T;
vector<int> a[N],l[N],r[N],up[N],down[N];
int n,m,k;
void init(vector<int> &a){
	a.push_back(0);
	for (int i=1;i<=m;i++) a.push_back(1);
	a.push_back(0);
}
void start(){
	scanf("%d%d%d",&n,&m,&k);
	for (int i=0;i<m+2;i++){
		a[0].push_back(0);
		l[0].push_back(0);
		r[0].push_back(0);
		up[0].push_back(0);
		down[0].push_back(0);
		a[n+1].push_back(0);
		l[n+1].push_back(0);
		r[n+1].push_back(0);
		up[n+1].push_back(0);
		down[n+1].push_back(0);
	}
	for (int i=1;i<=n;i++){
		init(a[i]);
		init(l[i]);
		init(r[i]);
		init(up[i]);
		init(down[i]);
	}
	for (int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=0;
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		l[i][j]=a[i][j]?l[i][j-1]+1:0;
	for (int i=1;i<=n;i++)
	for (int j=m;j;j--)
		r[i][j]=a[i][j]?r[i][j+1]+1:0;
	for (int j=1;j<=m;j++)
	for (int i=1;i<=n;i++)
		up[i][j]=a[i][j]?up[i-1][j]+1:0;
	for (int j=1;j<=m;j++)
	for (int i=n;i;i--)
		down[i][j]=a[i][j]?down[i+1][j]+1:0;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		r[i][j]=min(l[i][j],r[i][j])-1;
		up[i][j]--;
		down[i][j]--;
	}
}
int main()
{
	freopen("bzoj_2727.in","r",stdin);
	freopen("bzoj_2727.out","w",stdout);
	start();
	int ans=0;
	for (int j=1;j<=m;j++){
		//printf("line %d:\n",j);
		int last=1;
		while (last<=n){
			int now=last;
			for (;a[now][j];now++);
			//printf("[%d,%d)\n",last,now);
			for (int i=last+2;i<now;i++){
				T.add(r[i-2][j],up[i-2][j]);
				ans=inc(ans,mul(down[i][j],mul(c2(r[i][j]),T.sum(r[i][j],N-1))));
			}
			for (int i=last+2;i<now;i++)
				T.add(r[i-2][j],p-up[i-2][j]);
			for (int i=last+2;i<now;i++){
				T.add(r[i-2][j],mul(up[i-2][j],r[i-2][j]));
				ans=inc(ans,mul(down[i][j],mul(r[i][j],T.sum(0,r[i][j]-1))));
			}
			for (int i=last+2;i<now;i++)
				T.add(r[i-2][j],p-mul(up[i-2][j],r[i-2][j]));
			for (int i=last+2;i<now;i++){
				T.add(r[i-2][j],mul(up[i-2][j],c2(r[i-2][j]+1)));
				ans=dec(ans,mul(down[i][j],T.sum(0,r[i][j]-1)));
			}
			for (int i=last+2;i<now;i++)
				T.add(r[i-2][j],p-mul(up[i-2][j],c2(r[i-2][j]+1)));
			last=now+1;
		}
	}
	printf("%d\n",ans);
	return 0;
}