【BZOJ2727】双十字（动态规划，树状数组）

题面

BZOJ

洛谷

题解

我们去年暑假的时候考试考过。

我当时写了个大暴力混了\(70\)分。。。。

大暴力是这么写的：

预处理每个位置向左右/上/下能够拓展的最多的长度(左右相当于分别求然后取\(min\))

接着枚举双十字的中轴线，所在的列

然后枚举上面那一行，枚举下面那一行。

那么，贡献显然是上面选择的左右长度\(*\)下面可以选择的左右长度\(*\)上下两行分别向上/下拓展的长度。

发现复杂度瓶颈在于枚举完上面那一行之后又去枚举下面那一行。

这个东西显然可以前缀和优化，那么每次修改都是一个区间加法，并且还是加等差数列。

线段树或者树状数组就好啦？

线段树怎么维护可以参考洛谷上那道无聊的数列

树状数组的做法，首先要知道怎么维护区间加法

核心思想是差分。

我们要加一个等差数列，如果只进行一次差分，那么就是给差分数组做区间加法。

这样显然还不行，所以我们对于差分数组再差分一次，假设得到的数组是\(c_i\)，原数组是\(a_i\)，差分一次的结果是\(b_i\)

那么

用树状数组维护\(c[i],ic[i],i^2c[i]\)即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define RG register

#define MAX 1500000

#define MOD 1000000009

#define inv2 500000005

#define id(x,y) ((x-1)*m+y)

inline int read()

{

	RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

bool vis[MAX];

int n,m,L[MAX],U[MAX],D[MAX],ans,K;

int c1[MAX],c2[MAX],c3[MAX];

inline int lb(int x){return x&(-x);}

void modify(int x,int w)

{

	for(int i=x;i<=m;i+=lb(i))

	{

		add(c1[i],w);

		add(c2[i],1ll*x*w%MOD);

		add(c3[i],1ll*x*x%MOD*w%MOD);

	}

}

int getsum(int x)

{

	int s1=0,s2=0,s3=0,ret=0;

	for(int i=x;i;i-=lb(i))

		add(s1,c1[i]),add(s2,c2[i]),add(s3,c3[i]);

	add(ret,(1ll*(x+3)*x%MOD+2)*s1%MOD);add(ret,s3);

	add(ret,MOD-1ll*(x+x+3)*s2%MOD);

	ret=1ll*ret*inv2%MOD;

	return ret;

}

void modify(int l,int r,int w){modify(l,w);modify(r+1,MOD-w);}

void init(){for(int i=1;i<=m;++i)c1[i]=c2[i]=c3[i]=0;}

int main()

{

	n=read();m=read();K=read();

	for(int i=1;i<=n*m;++i)vis[i]=true;

	while(K--)vis[id(read(),read())]=false;

	for(int i=1;i<=n;++i)//Left

	{

		int s=0,now=(i-1)*m+1;

		for(int j=1;j<=m;++j,++now)

		{

			s=vis[now]?s+1:0;

			L[now]=s;

		}

	}

	for(int i=1;i<=n;++i)//Right

	{

		int s=0,now=i*m;

		for(int j=m;j>=1;--j,--now)

		{

			s=vis[now]?s+1:0;

			L[now]=min(L[now],s);if(L[now])--L[now];

		}

	}

	for(int j=1;j<=m;++j)//Up

	{

		int s=0,now=j;

		for(int i=1;i<=n;++i,now+=m)

		{

			s=vis[now]?s+1:0;

			U[now]=s;if(U[now])--U[now];

		}

	}

	for(int j=1;j<=m;++j)//Down

	{

		int s=0,now=id(n,j);

		for(int i=n;i>=1;--i,now-=m)

		{

			s=vis[now]?s+1:0;

			D[now]=s;if(D[now])--D[now];

		}

	}

	for(int j=2;j<m;++j,init())

		for(int i=3;i<n;++i)

		{

			int u=id(i,j);

			if(!vis[u]){init();continue;}

			if(L[u])add(ans,1ll*D[u]*getsum(L[u]-1)%MOD);

			modify(1,L[u-m],U[u-m]);

		}

	printf("%d\n",ans);

	return 0;

}