【Foreign】画方框 [主席树]

画方框

Time Limit: 10 Sec Memory Limit: 256 MB

Description

Input

Output

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

Sample Input

　　3
　　1 1 1
　　1 0 1
　　1 1 1

Sample Output

HINT

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 #include<iostream>    
  2 #include<string>    
  3 #include<algorithm>    
  4 #include<cstdio>    
  5 #include<cstring>    
  6 #include<cstdlib>
  7 #include<cmath>
  8 #include<queue>
  9 using namespace std;  
 10 typedef long long s64;
 11   
 12 const int ONE = 1005;
 13 const int INF = 10001;
 14 
 15 int n;
 16 int a[ONE][ONE];
 17 int Ans;
 18 
 19 struct power
 20 {
 21         int left, right;
 22         int up, down;
 23         int L, R;
 24 }A[ONE][ONE];
 25 
 26 int cnt, res;
 27 struct point
 28 {
 29         int root;
 30         int value;
 31         int left, right;
 32 }Node[ONE * 19];
 33 
 34 int get()
 35 {
 36         int res=1,Q=1;char c;
 37         while( (c=getchar())<48 || c>57 ) 
 38         if(c=='-')Q=-1; 
 39         res=c-48;     
 40         while( (c=getchar())>=48 && c<=57 )    
 41         res=res*10+c-48;    
 42         return res*Q;
 43 }
 44 
 45 void Deal_first()
 46 {
 47         for(int i = 1; i <= n; i++)
 48         {
 49             for(int j = n; j >= 1; j--)
 50                 if(a[i][j]) A[i][j].right = A[i][j + 1].right + 1;
 51                 else A[i][j].right = 0;
 52             for(int j = 1; j <= n; j++)
 53                 if(a[i][j]) A[i][j].left = A[i][j - 1].left + 1;
 54                 else A[i][j].left = 0;
 55         }
 56         
 57         for(int j = 1; j <= n; j++)
 58         {
 59             for(int i = n; i >= 1; i--)
 60                 if(a[i][j]) A[i][j].down = A[i + 1][j].down + 1;
 61                 else A[i][j].down = 0;
 62             for(int i = 1; i <= n; i++)
 63                 if(a[i][j]) A[i][j].up = A[i - 1][j].up + 1;
 64                 else A[i][j].up = 0;
 65         }
 66         
 67         for(int i = 1; i <= n; i++)
 68             for(int j = 1; j <= n; j++)
 69                 A[i][j].L = min(A[i][j].left, A[i][j].up),
 70                 A[i][j].R = min(A[i][j].right, A[i][j].down);
 71 }
 72 
 73 void Update(int &x, int y, int L, int R, int Q, int val)
 74 {
 75         x = ++cnt;
 76         Node[x].left = Node[y].left;
 77         Node[x].right = Node[y].right;
 78         Node[x].value = Node[y].value + val;
 79         if(L == R) return;
 80          
 81         int M = L + R >> 1;
 82         if(Q <= M)
 83             Update(Node[x].left, Node[y].left, L, M, Q, val);
 84         else
 85             Update(Node[x].right, Node[y].right, M + 1, R, Q, val);
 86 }
 87 
 88 void Query(int x, int y, int l, int r, int L, int R)
 89 {
 90         if(L <= l && r <= R)
 91         {
 92             res += Node[y].value - Node[x].value;
 93             return;
 94         }
 95          
 96         int mid = l + r >> 1;
 97         
 98         if(L <= mid) Query(Node[x].left, Node[y].left, l, mid, L, R);
 99         if(mid + 1 <=R) Query(Node[x].right, Node[y].right, mid + 1, r, L, R);
100 }
101   
102 
103 int main()
104 {
105         n = get();
106         for(int i = 1; i <= n; i++)
107             for(int j = 1; j <= n; j++)
108                 a[i][j] = get();
109             
110         Deal_first();
111         
112         for(int id = 1; id <= n; id++)
113         {
114             for(int x = id, y = 1; x <= n; x++, y++)
115                 Update(Node[y].root, Node[y - 1].root, 1, INF, y - A[x][y].L + 1, 1);
116                     
117             for(int x = id, y = 1; x <= n; x++, y++)
118             {
119                 res = 0;
120                 if(A[x][y].R)
121                     Query(Node[y - 1].root, Node[y + A[x][y].R - 1].root, 1, INF, 1, y);
122                 Ans += res;
123             }
124             
125             cnt = 0;
126             for(int i = 1; i <= cnt; i++)
127                 Node[i].left = Node[i].right = Node[i].root = Node[i].value = 0; 
128         }
129         
130         for(int id = 2; id <= n; id++)
131         {
132             for(int y = id, x = 1; y <= n; y++, x++)
133                 Update(Node[x].root, Node[x - 1].root, 1, INF, x - A[x][y].L + 1, 1);
134                     
135             for(int y = id, x = 1; y <= n; y++, x++)
136             {
137                 res = 0;
138                 if(A[x][y].R)
139                     Query(Node[x - 1].root, Node[x + A[x][y].R - 1].root, 1, INF, 1, x);
140                 Ans += res;
141             }
142             
143             cnt = 0;
144             for(int i = 1; i <= cnt; i++)
145                 Node[i].left = Node[i].right = Node[i].root = Node[i].value = 0; 
146         }
147         
148         printf("%d", Ans);
149 }

View Code