画方框

Time Limit: 10 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

输出一行一个整数，表示 CD 最多可能画了几个方框。

Sample Input

3
　　1 1 1
　　1 0 1
　　1 1 1

Sample Output

9

HINT

img

Main idea

给定一个01矩阵，1表示有标记，询问正方形方框的个数。

Solution

首先，我们先从 维护对角线上的点 这一层面来考虑。

我们先把一个点 能向左向上拓展的最大长度 以及 能向右向下的最长长度 预处理出来。

那么这时候，我们考虑 对于一条对角线上的点 怎么 在O(nlogn)以内 统计出答案。必然要用到某些数据结构。

举个例子，比如这个数据：
　　　　　　1 1 1 1
　　　　　　1 0 0 0
　　　　　　1 0 0 1
　　　　　　1 0 1 1
　　　　我们现在统计中间对角线的答案。
　　　　现在查询第一个点(1,1)，他向右向下拓展长度为 4 。
　　　　就是查询，后面三个点中 可以向左上拓展的长度 (2,2)>=1 (3,3)>=2 (4,4)>=3，
　　　　这三个条件满足了几个。

这样的话，我们发现：每次统计一个点的时候 查询的就是：在这个点 可以向右向下拓展 到的范围内，它后面的第 i 个点 可以向左向上拓展长度 是否 > i。

我们发现：查询后面若干个数的值是否 > 一个等差数列比较复杂。

于是乎，若统计第id个的答案，后面第num个点（在向右向下范围内）可以被统计所需要满足的条件是：num - id + 1 <= val 也就是 num - val + 1 <= id。（其中val表示 这个点可以向左向上拓展的长度）

所以我们如果把 i - val + 1 加入到一个数据结构中的话，

查询的就是：某一范围内 <=一个定值 的数的个数。

那直接用主席树来做就好了。

这样我们就解决了这个问题 QWQ。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1005;
const int INF = 10001;

int n;
int a[ONE][ONE];
int Ans;

struct power
{
    int left, right;
    int up, down;
    int L, R;
}A[ONE][ONE];

int cnt, res;
struct point
{
    int root;
    int value;
    int left, right;
}Node[ONE * 19];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Deal_first()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = n; j >= 1; j--)
            if(a[i][j]) A[i][j].right = A[i][j + 1].right + 1;
        else A[i][j].right = 0;
        for(int j = 1; j <= n; j++)
            if(a[i][j]) A[i][j].left = A[i][j - 1].left + 1;
        else A[i][j].left = 0;
    }

    for(int j = 1; j <= n; j++)
    {
        for(int i = n; i >= 1; i--)
            if(a[i][j]) A[i][j].down = A[i + 1][j].down + 1;
        else A[i][j].down = 0;
        for(int i = 1; i <= n; i++)
            if(a[i][j]) A[i][j].up = A[i - 1][j].up + 1;
        else A[i][j].up = 0;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            A[i][j].L = min(A[i][j].left, A[i][j].up),
    A[i][j].R = min(A[i][j].right, A[i][j].down);
}

void Update(int &x, int y, int L, int R, int Q, int val)
{
    x = ++cnt;
    Node[x].left = Node[y].left;
    Node[x].right = Node[y].right;
    Node[x].value = Node[y].value + val;
    if(L == R) return;

    int M = L + R >> 1;
    if(Q <= M)
        Update(Node[x].left, Node[y].left, L, M, Q, val);
    else
        Update(Node[x].right, Node[y].right, M + 1, R, Q, val);
}

void Query(int x, int y, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
    {
        res += Node[y].value - Node[x].value;
        return;
    }

    int mid = l + r >> 1;

    if(L <= mid) Query(Node[x].left, Node[y].left, l, mid, L, R);
    if(mid + 1 <=R) Query(Node[x].right, Node[y].right, mid + 1, r, L, R);
}


int main()
{
    n = get();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            a[i][j] = get();

    Deal_first();

    for(int id = 1; id <= n; id++)
    {
        for(int x = id, y = 1; x <= n; x++, y++)
            Update(Node[y].root, Node[y - 1].root, 1, INF, y - A[x][y].L + 1, 1);

        for(int x = id, y = 1; x <= n; x++, y++)
        {
            res = 0;
            if(A[x][y].R)
                Query(Node[y - 1].root, Node[y + A[x][y].R - 1].root, 1, INF, 1, y);
            Ans += res;
        }

        cnt = 0;
        for(int i = 1; i <= cnt; i++)
            Node[i].left = Node[i].right = Node[i].root = Node[i].value = 0;
    }

    for(int id = 2; id <= n; id++)
    {
        for(int y = id, x = 1; y <= n; y++, x++)
            Update(Node[x].root, Node[x - 1].root, 1, INF, x - A[x][y].L + 1, 1);

        for(int y = id, x = 1; y <= n; y++, x++)
        {
            res = 0;
            if(A[x][y].R)
                Query(Node[x - 1].root, Node[x + A[x][y].R - 1].root, 1, INF, 1, x);
            Ans += res;
        }

        cnt = 0;
        for(int i = 1; i <= cnt; i++)
            Node[i].left = Node[i].right = Node[i].root = Node[i].value = 0;
    }

    printf("%d", Ans);
}