（Educational Codeforces Round 8） E Zbazi in Zeydabad （树状数组优化暴力）

题目链接：

http://codeforces.com/contest/628/problem/E

题意：

问n*m （1<=n,m<=3000) 的矩阵中有多少个由z组成的Z。

做法：

先求出每个z向左，向右，向做下延伸的最大距离。

然后就是以每个z为右上角，设当前的z的坐标是(X,Y),设len=min(l[X][Y],ld[X][Y]),那么就是要查询从(X,Y)到(X+len-1,Y-len+1)的路径上有多少个坐标(x',y')满足y'+r[x'][y']-1>=Y。

思路其实很简单，暴力找的话总复杂度是O（n^3）。我们可以用树状数组优化查询的部分。

设路径上的z坐标为(x',y')，我们在(x',y'+r[x'][y']-1)这个位置涂上颜色，那么其实会发现满足条件的z对应的涂色的地方都在一个矩阵里。这个矩阵的x坐标属于【X，X+len-1】,矩阵里被涂色的方块个数就是我们要查询的答案。

可以用二维树状数组来求矩阵里的和。不过发现如果从左下角开始一直往右上角依次查询的话，当前点左下部分那些涂色的地方之后就不会用到了，所以建立x坐标的树状数组，把那些没用的点去掉，就可以了。

cf的题目质量真的高。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m;
long long ans;
int l[N][N],r[N][N],ld[N][N];//左，右，左下延伸的距离
int c[N];//x坐标的树状数组
char s[N][N];
vector<int>vec[N]; //用来去掉已经没用的涂色方块
void add(int x,int y)
{
	for (int i=x;i<N;i+=i&-i) c[i]+=y;
}
int get(int x)
{
	int tmp=0;
	for (int i=x;i;i-=i&-i) tmp+=c[i];
	return tmp;
}
void cal(int x,int y)
{
	for (int i=0;i<N;i++) c[i]=0,vec[i].clear();
	for (;x>=1&&y<=m;x--,y++)
	{
		if (s[x][y]=='z')
		{
			add(x,1);//(x,y+r[x][y]-1)的位置被涂色
			vec[y+r[x][y]-1].push_back(x);// 在涂色的那一列存下x坐标，等待删除
			ans+=get(x+min(l[x][y],ld[x][y])-1)-get(x-1);//统计查询的矩阵里的涂色块
		}
		for (int i=0;i<vec[y].size();i++) add(vec[y][i],-1); //去掉y所在那一列没用的涂色块
		vec[y].clear();
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			if (s[i][j]=='z') l[i][j]=l[i][j-1]+1;
		for (int j=m;j>=1;j--)
			if (s[i][j]=='z') r[i][j]=r[i][j+1]+1;
	}
	for (int i=n;i>=1;i--)
		for (int j=1;j<=m;j++)
		 	if (s[i][j]=='z') ld[i][j]=ld[i+1][j-1]+1;
	for (int i=1;i<=n;i++) cal(i,1); //从边界开始往右上角统计
	for (int j=2;j<=m;j++) cal(n,j); //从边界开始往右上角统计
	printf("%I64d\n",ans);
}