$ >Codeforces \space 372 B. ?Counting?Rectangles?is?Fun<$
題目大意 :
給出一個 \(n \times m\) 的 \(01\) 矩陣，有 \(q\) 次詢問，每次給出一個矩形 $ x_1, x_2, y_1, y_2$ ，求有多這個矩形的有多少個全 \(0\) 子矩形
\(1 \leq n, m \leq 50, 1 \leq q \leq 3 \times 10^5\)
解題思路 :
設 \(g(x, y, l, r)\) 表示以 \(x\) 為底，滿足上邊界 \(\leq y\) , 左邊界 \(\geq l\) ，右邊界 \(\leq r\) 的矩形的數量
那么對于一組詢問 \(x_1, x_2, y_1, y_2\)，\(Ans = \sum_{i = x_1}^{x_2} g(x_2, x_1, y_1, y_2)\)
所以直接考慮怎么求 \(g(x, y, l, r)\) 即可，問題轉化為上下左右邊界已經框好，求有多少個貼著下邊界的全 \(0\) 子矩形
考慮維護一條從左邊界到右邊界的掃描線，每次計算當前的右端點向左延伸形成的子矩形的個數
考慮對于當前右端點 \(r\) 有一個左端點 \(l\), 設 \(len(x, y)\) 表示從點 \((x, y)\) 向上能延伸的 \(0\) 的個數
那么 \(l, r\) 作為左右端點能形成的全 \(0\) 子矩形的個數就是 \(\min(len(x, j))\ \ l \leq j \leq r\)
觀察發現，對于每一個區間的答案其實就是這個區間 \(len\) 的最小值，直接枚舉左端點并用單調棧維護即可
此時求 \(g\) 的復雜度是 \(O(n^5)\) 級別，由于 \(n, m\) 很小只有 \(40\) 所以可以接受，之后的詢問可以直接預處理答案，總復雜度是 \(O(n^5 + q)\)
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){int f = 0, ch = 0; x = 0;for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;if(f) x = -x;
}
#define N (45)
#define x1 xx1
#define y1 yy1
#define x2 xx2
#define y2 yy2
char s[N][N];
int f[N][N][N][N], g[N][N], xx[N], ff[N], n, m, q, top;
int main(){read(n), read(m), read(q);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++){int tot = 0;for(int k = i; k >= 1; k--, tot++)if(s[k][j] == '1') break;g[i][j] = tot;}for(int x1 = 1; x1 <= n; x1++) for(int x2 = x1; x2 <= n; x2++)for(int y1 = 1; y1 <= m; y1++){int res = 0; top = 0, xx[0] = y1 - 1;for(int y2 = y1; y2 <= m; y2++){int len = Min(x2 - x1 + 1, g[x2][y2]);while(top && len <= ff[top]) top--;xx[++top] = y2, ff[top] = len;for(int i = top; i >= 1; i--) res += (xx[i] - xx[i-1]) * ff[i];f[x1][y1][x2][y2] = res;}}for(int x1 = 1; x1 <= n; x1++)for(int x2 = x1; x2 <= n; x2++)for(int y1 = 1; y1 <= m; y1++)for(int y2 = y1; y2 <= m; y2++) if(x2 > x1) f[x1][y1][x2][y2] += f[x1][y1][x2-1][y2];for(int i = 1, x1, x2, y1, y2; i <= q; i++){read(x1), read(y1), read(x2), read(y2);printf("%d\n", f[x1][y1][x2][y2]);} return 0;
}
轉載于:https://www.cnblogs.com/mangoyang/p/9464388.html
總結
以上是生活随笔為你收集整理的Codeforces 372 B. Counting Rectangles is Fun的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
