题目链接：

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);
}

htw学长用线段树做这道，一直RE，后来发现是没有考虑子节点越界。我看这道题很像扫描线，离散化后用堆维护当前最靠前的海报，1A.

代码可比线段树短多了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
struct line{
    bool operator< (const line &a)const
    {
        return no<a.no;
    }
    int x,y;
    int no;
}a[10005];
bool cmpq(line a,line b){return a.no<b.no;}
bool cmp(int i,int j){return a[i].x<a[j].x;}
int n,i,j,t,ans,tot;
int c[50005],node[10005];
bool b[10005];
void lisan()
{
    sort(c+1,c+tot+1);
    int now=1;
    for (i=2;i<=tot;i++)
      if (c[i]>c[now]) c[++now]=c[i];
    tot=now;
}
void init()
{
    ans=0; tot=0;
    memset(b,0,sizeof(b));
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y),a[i].no=i,node[i]=i;
            c[++tot]=a[i].x; c[++tot]=a[i].x+1;
            c[++tot]=a[i].y; c[++tot]=a[i].y+1;
        }
        sort(node+1,node+n+1,cmp);
        lisan();
        j=1;
        priority_queue<line>q;
        for (i=1;i<=tot;i++)
        {
            while(!q.empty()&&q.top().y<c[i]) q.pop();
            while(j<=n&&a[node[j]].x<=c[i]) q.push(a[node[j]]),j++;
            if (!q.empty()) b[q.top().no]=1;
        }
        for (i=1;i<=n;i++) if (b[i]) ans++;
        printf("%d\n",ans);
    }
}