这个题和一个CF上的找"Z"的题差不多，都是扫描线+树状数组
从右上角的主对角线开始扫描，一直扫到左下角，每次更新，右延伸等于该扫描线的点，注意在其所在的树状数组更新就好了
时间复杂度O（n^2logn)
#include <stdio.h> #include <iostream> #include <vector> #include <math.h> #include <set> #include <map> #include <queue> #include <algorithm> #include <string.h> #include <string> using namespace std; typedef long long LL; const LL mod=1e8+7; const int N=1e3+5; int c[2005][N],n,m; char s[N][N]; int r[N][N],xl[N][N],xr[N][N]; struct Point { int x,y; }; vector<Point>g[2005]; void add(int pos,int x) { for(int i=x; i<=m; i+=i&(-i)) ++c[pos][i]; } int sum(int pos,int x) { int ans=0; if(x==0)return 0; for(int i=x; i>0; i-=i&(-i)) ans+=c[pos][i]; return ans; } int main() { int T,cas=0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1; i<=n+m; ++i)g[i].clear(); for(int i=1; i<=n; ++i)scanf("%s",s[i]+1); memset(xl,0,sizeof(xl)); memset(xr,0,sizeof(xr)); memset(r,0,sizeof(r)); memset(c,0,sizeof(c)); for(int j=m; j>0; --j) for(int i=1; i<=n; ++i) if(s[i][j]=='x')r[i][j]=r[i][j+1]+1; for(int i=n; i>0; --i) for(int j=1; j<=m; ++j) if(s[i][j]=='x')xl[i][j]=xl[i+1][j-1]+1,xr[i][j]=xr[i+1][j+1]+1; for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) if(s[i][j]=='x') { int x=i,y=j+r[i][j]-1; if(x<y)y-=(x-1),x=1; else x-=(y-1),y=1; Point tmp; tmp.x=i,tmp.y=j; int id; if(x==1)id=y; else id=m+x; g[id].push_back(tmp); } int res=0; for(int i=m; i>=1; --i) { for(int j=0; j<g[i].size(); ++j) { int pos=g[i][j].x+g[i][j].y; add(pos,g[i][j].y); } for(int x=1,y=i; x<=n&&y<=m; ++x,++y) { if(s[x][y]!='x')continue; int l=min(xl[x][y],xr[x][y]); res+=sum(x+y,y)-sum(x+y,y-l); } } for(int i=2; i<=n; ++i) { for(int j=0; j<g[m+i].size(); ++j) { int pos=g[i+m][j].x+g[i+m][j].y; add(pos,g[i+m][j].y); } for(int x=i,y=1; x<=n&&y<=m; ++x,++y) { if(s[x][y]!='x')continue; int l=min(xl[x][y],xr[x][y]); res+=sum(x+y,y)-sum(x+y,y-l); } } printf("Case #%d: %d ",++cas,res); } return 0; }