[LOJ#3177][IOI2019]矩形區域（分治 + 單調棧）

Address

• LOJ #3177

Solution

• 首先有一個性質
• 對于長度為 n n n 的數組 a 1... n a_{1...n} a1...n​
• 滿足對于所有 l ≤ i ≤ r l\le i\le r l≤i≤r 都有 a l − 1 > a i , a r + 1 > a i a_{l-1}>a_i,a_{r+1}>a_i al−1​>ai​,ar+1​>ai​ 的二進制組 ( l , r ) (l,r) (l,r) 隻有 O ( n ) O(n) O(n) 個
• 證明可以使用單調棧
• 把這個性質放回原問題
• 相當于如果某一行強制被選出，那麼合法的列區間隻有 O ( m ) O(m) O(m) 個
• 同樣地，如果某一列強制被選出，那麼合法的行區間也隻有 O ( n ) O(n) O(n) 個
• 取 m i d = ⌊ 1 + n 2 ⌋ mid=\lfloor\frac{1+n}2\rfloor mid=⌊21+n​⌋ ，考慮統計過第 m i d mid mid 行的子矩形數量，即第 m i d mid mid 行被強制選出
• 先利用單調棧枚舉出所有合法的列區間 [ l , r ] [l,r] [l,r]
• 現在要做的就是統計有多少個合法子矩形，行區間包含了 m i d mid mid 且列區間為 [ l , r ] [l,r] [l,r]
• 列區間為 [ l , r ] [l,r] [l,r] 相當于第 l l l 列到第 r r r 列都被強制選出
• 故這時合法的行區間隻有 O ( n ) O(n) O(n) 個，同樣使用單調棧枚舉這樣的行區間
• 然後就是判定一個子矩形是否合法了
• 這個可以各憑本事求，下面的代碼裡使用的是預處理每個數往上 / 下第一個不小于自己的數所在位置後用 RMQ 判定
• 而至于不過第 m i d mid mid 行的子矩形，分治處理即可
• O ( n m ( log ⁡ n + log ⁡ m ) ) O(nm(\log n+\log m)) O(nm(logn+logm))
• 如果有 O ( n m ) O(nm) O(nm) 做法歡迎提出

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}

template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}

const int N = 2505, M = N << 1, LogN = 12;

int n, m, a[N][N], top, stk[N], tot, L[M], R[M], le[N][N], ri[N][N],
up[N][N][LogN], dn[N][N][LogN], Log[N], ans;

int upmax(int i, int l, int r)
{
	int k = Log[r - l + 1];
	return Max(up[i][l][k], up[i][r - (1 << k) + 1][k]);
}

int dnmin(int i, int l, int r)
{
	int k = Log[r - l + 1];
	return Min(dn[i][l][k], dn[i][r - (1 << k) + 1][k]);
}

bool avail(int xl, int xr, int yl, int yr)
{
	return dnmin(xl - 1, yl, yr) > xr && upmax(xr + 1, yl, yr) < xl;
}

void solve(int l, int r)
{
	if (l > r) return;
	int mid = l + r >> 1;
	top = tot = 0;
	for (int i = 1; i <= m; i++)
	{
		while (top && a[mid][i] > a[mid][stk[top]])
		{
			if (stk[top] + 1 < i) L[++tot] = stk[top] + 1, R[tot] = i - 1;
			top--;
		}
		if (top && stk[top] + 1 < i) L[++tot] = stk[top] + 1, R[tot] = i - 1;
		stk[++top] = i;
	}
	for (int i = 1; i <= tot; i++)
	{
		top = 0; int x = L[i], il = mid, ir = mid;
		while (il > l - 1 && ri[il][L[i] - 1] > R[i]
			&& le[il][R[i] + 1] < L[i]) il--;
		while (ir < r + 1 && ri[ir][L[i] - 1] > R[i]
			&& le[ir][R[i] + 1] < L[i]) ir++;
		for (int j = il; j <= ir; j++)
		{
			while (top && a[j][x] > a[stk[top]][x])
			{
				if (stk[top] + 1 <= mid && j - 1 >= mid
					&& avail(stk[top] + 1, j - 1, L[i], R[i])) ans++;
				top--;
			}
			if (top && stk[top] + 1 <= mid && j - 1 >= mid
				&& avail(stk[top] + 1, j - 1, L[i], R[i])) ans++;
			stk[++top] = j;
		}
	}
	solve(l, mid - 1); solve(mid + 1, r);
}

int main()
{
	read(n); read(m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			read(a[i][j]);
	for (int i = 1; i <= n; i++)
	{
		stk[top = 0] = 0;
		for (int j = 1; j <= m; j++)
		{
			while (top && a[i][j] > a[i][stk[top]]) top--;
			le[i][j] = stk[top]; stk[++top] = j;
		}
		stk[top = 0] = m + 1;
		for (int j = m; j >= 1; j--)
		{
			while (top && a[i][j] > a[i][stk[top]]) top--;
			ri[i][j] = stk[top]; stk[++top] = j;
		}
	}
	for (int j = 1; j <= m; j++)
	{
		stk[top = 0] = 0;
		for (int i = 1; i <= n; i++)
		{
			while (top && a[i][j] > a[stk[top]][j]) top--;
			up[i][j][0] = stk[top]; stk[++top] = i;
		}
		stk[top = 0] = n + 1;
		for (int i = n; i >= 1; i--)
		{
			while (top && a[i][j] > a[stk[top]][j]) top--;
			dn[i][j][0] = stk[top]; stk[++top] = i;
		}
	}
	Log[0] = -1;
	for (int i = 1; i <= m; i++) Log[i] = Log[i >> 1] + 1;
	for (int i = 1; i <= n; i++)
		for (int k = 1; k <= 11; k++)
			for (int j = 1; j + (1 << k) - 1 <= m; j++)
			{
				up[i][j][k] = Max(up[i][j][k - 1], up[i][j + (1 << k - 1)][k - 1]);
				dn[i][j][k] = Min(dn[i][j][k - 1], dn[i][j + (1 << k - 1)][k - 1]);
			}
	solve(2, n - 1);
	return std::cout << ans << std::endl, 0;
}