5 seconds
512 megabytes
standard input
standard output
A tourist wants to visit country Zeydabad for Zbazi (a local game in Zeydabad).
The country Zeydabad is a rectangular table consisting of n rows and m columns. Each cell on the country is either 'z' or '.'.
The tourist knows this country is named Zeydabad because there are lots of ''Z-pattern"s in the country. A ''Z-pattern" is a square which anti-diagonal is completely filled with 'z' and its upper and lower rows are also completely filled with 'z'. All other cells of a square can be arbitrary.
Note that a ''Z-pattern" can consist of only one cell (see the examples).
So he wants to count the number of ''Z-pattern"s in the country (a necessary skill for Zbazi).
Now your task is to help tourist with counting number of ''Z-pattern"s.
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to usegets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead ofScanner/System.out in Java.
The first line contains two integers n, m (1 ≤ n, m ≤ 3000) — the number of rows and columns respectively.
Each of the next n lines contains m characters 'z' or '.' — the description of Zeydabad.
Print the only integer a — the number of ''Z-pattern"s in Zeydabad.
4 4
zzzz
zzz.
.z..
zzzz
16
1 4
z.z.
2
2 2
zz
zz
5
题意：
给出一个n*n的矩阵，问有多少个子矩阵满足副对角线、最上面的行、最下面的行都是由z构成（其他位置无关）（理解一下，这样的图形构成了一个Z的图案）。
题解：
如果预处理出每个点向左向右连续的z能够有多长，
那么先枚举副对角线，
由于答案肯定是由副对角线上连续的一段z贡献的，
所以我们可以一段段z来做。
问题转换成了，在这一段z上，有多少个点对（i，j）满足
left[i]>=j - i, right[j] >= j - i，
也就是说，i、j必须能够分别用left[i]、right[j]的长度分别覆盖对方。 那么我们可以枚举j，确定有多少i对它进行了贡献。
那么对于每个i，我们都能够知道它最远能够贡献到哪里，
每当我们的j超过了这个i最远能贡献的距离，就将它排去，
因为i不可能再对能够覆盖它的j左贡县。
对于每个j，现在所有能够留下来的i都是能够覆盖它的。
能够对它有贡献的i就是那些它能覆盖的i。 所以保持i能覆盖当前的j这一步可以使用优先队列完成，
统计有多少i贡献j能够用树状数组完成。 挺水的。
#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define clr(x, y) memset(x, y, sizeof(x))
#define mk make_pair const int N = ;
typedef long long ll;
int n, m;
char graph[N][N];
int lef[N][N], rig[N][N]; ll sum[N];
priority_queue<pair<int, int> > outQue; int lowbit(int x) {
return x & (-x);
} int len;
void add(ll *arr, int pos, ll val) {
if(!pos) return;
for(int x = pos; x <= len; x += lowbit(x)) arr[x] += val;
} ll query(ll *arr, int pos) {
ll ret = ;
for(int x = pos; x; x -= lowbit(x)) ret += arr[x];
return ret;
} ll query(ll *arr, int lef, int rig) {
ll b = query(arr, rig);
ll a = query(arr, lef - );
return b - a;
} void solve() {
for(int i = ; i <= n; ++i) {
lef[i][] = ;
for(int j = ; j <= m; ++j)
if(graph[i][j] == '.') lef[i][j] = ;
else lef[i][j] = lef[i][j - ] + ;
lef[i][m + ] = ;
for(int j = m; j >= ; --j)
if(graph[i][j] == '.') rig[i][j] = ;
else rig[i][j] = rig[i][j + ] + ;
} ll ans = ;
for(int diagon = ; diagon <= n + m - ; ++diagon) {
int stx = max(, diagon - m + ), sty = min(diagon, m);
int tot = ;
bool first = true;
for(int x = stx, y = sty; x <= n && y >= ; ++x, --y)
if(graph[x][y] == '.') {
for(int i = ; i <= tot; ++i) sum[i] = ;
while(!outQue.empty()) outQue.pop();
tot = , first = true;
} else {
if(first) {
len = , first = false;
for(int _x = x, _y = y; _x <= n && _y >= && graph[_x][_y] == 'z'; ++_x, --_y)
++len;
}
++tot;
add(sum, tot, );
outQue.push(mk(-(tot + lef[x][y] - ), tot)); while(-outQue.top().first < tot) {
add(sum, outQue.top().second, -);
outQue.pop();
} ll tmp = query(sum, max(, tot - rig[x][y] + ), tot);
ans += tmp;
}
for(int i = ; i <= tot; ++i) sum[i] = ;
while(!outQue.empty()) outQue.pop();
} cout << ans << endl;
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i) scanf("%s", graph[i] + );
solve();
return ;
}