专栏文章

Silksong

冷冷却心月明かり
P5781题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio5dgxh
此快照首次捕获于
2025/12/02 13:38
3 个月前
此快照最后确认于
2025/12/02 13:38
3 个月前
查看原文
笑点解析：模拟赛赛时想完前面全部最后一步糖糖统计不会做赫赫，但是丝之歌要发售了好耶。
先考虑序列情况。相当于求出所有区间 [l,r][l,r] 满足 max⁡l≤i≤rai<min⁡{al−1,ar+1}\max_{l\le i\le r} a_i < \min\{a_{l-1},a_{r+1}\}。我们可以两端 al−1,ar+1a_{l-1},a_{r+1} 中较小的一个，那么另一侧就是往左或右第一个大于等于他的位置，单调栈能简单 O(n)\mathcal O(n) 求出，于是发现一个性质：这样的区间只有 O(n)\mathcal O(n) 个。
放到网格上，先 O(n2)\mathcal O(n^2) 求出若干个集合 S[l,r]S_{[l,r]} 表示合法区间有 [l,r][l,r] 的行集合，显然所有集合大小之和为 O(n2)\mathcal O(n^2)。考虑统计答案，我们从左往右枚举合法矩形的右边界 rr，同时维护若干指针 p[u,d]p_{[u,d]} 表示列方向上从第 rr 列往前合法区间都有 [u,d][u,d] 的列的左端点最左的位置。具体维护方式考虑求出当前列的合法区间集合，不在该集合内的区间的 pp 值赋值为 n+1n+1 表示非法，在集合内的区间的 pp 值和 rr 取较小值，直接维护是 O(n2)\mathcal O(n^2)，可以同时维护一个时间戳 t[l,r]t_{[l,r]} 表示上一次更新 [l,r][l,r] 的右边界，这样做到 O(n)\mathcal O(n) 更新 pp 指针。然后枚举矩形左边界 ll，那么合法矩形的上下边界 [u,d][u,d] 一定完全包含于集合 S[l,r]S_{[l,r]}，换言之，对于 S[l,r]S_{[l,r]} 内所有的极长连续段 [x,y][x,y]，他的贡献是所有 x≤a≤b≤yx\le a \le b \le y 中 p[a,b]≤lp_{[a,b]} \le l 的个数，这样行列要求均已满足。具体实现我们在 p[a,b]p_{[a,b]} 的位置插入区间 [a,b][a,b] 那么从左往右枚举 ll，就是每次对极长段 [l,r][l,r] 询问多少个 [a,b][a,b] 满足 l≤a≤b≤rl\le a\le b\le r，是一个二维数点，可以直接套 BIT 做完，但其实精细实现发现可以直接单调栈，原因是合法区间一定无交或包含，不会部分相交，所以直接单调栈统计。
视实现时间复杂度 O(n2log⁡n)\mathcal O(n^2 \log n) 或者 O(n2)\mathcal O(n^2)，n,mn,m 同阶。细节很少。
CPP
#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define LL long long
using namespace std;
const int N = 2.5e3 + 10;
int n, m, A[N][N], tmp[N]; LL Ans = 0;

int stk[N], tp;
void GetValidSegs(int* A, int n, vector<pair<int, int> >& res) {
	stk[tp = 1] = 1;
	for (int i = 2; i <= n; i ++) {
		while (tp && A[stk[tp]] < A[i]) tp --;
		if (tp && stk[tp] + 1 < i) res.push_back({stk[tp] + 1, i - 1});
		stk[++ tp] = i;
	}
	stk[tp = 1] = n;
	for (int i = n - 1; i >= 1; i --) {
		while (tp && A[stk[tp]] < A[i]) tp --;
		if (tp && stk[tp] - 1 > i && A[stk[tp]] != A[i]) res.push_back({i + 1, stk[tp] - 1});
		stk[++ tp] = i;
	} return ;
}

vector<int> col[N][N]; int lst[N][N], toki[N][N];
vector<pair<int, int> > ins[N]; vector<int> upd[N];

int tr[N], opt[N], len;
void add(int u, int k) { opt[++ len] = u; for (int i = u; i <= n; i += i & -i) tr[i] += k; }
int query(int u) { int r = 0; for (int i = u; i; i ^= i & -i) { r += tr[i]; } return r; }
void clear() {
	for (int i = 1; i <= len; i ++) for (int j = opt[i]; j <= n; j += j & -j) tr[j] = 0;
	len = 0; return ;
}

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) cin >> A[i][j];
	for (int i = 1; i <= n; i ++) {
		vector<pair<int, int> > vec; GetValidSegs(A[i], m, vec);
		for (auto [l, r] : vec) col[l][r].push_back(i);
	} 
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) toki[i][j] = 250904;
	for (int i = 1; i <= m; i ++) {
		for (int j = 1; j <= n; j ++) tmp[j] = A[j][i];
		vector<pair<int, int> > vec; GetValidSegs(tmp, n, vec);
		for (auto [l, r] : vec) {	
			if (toki[l][r] != i - 1) lst[l][r] = i;
			toki[l][r] = i; ins[lst[l][r]].push_back({l, r});
		}
		for (int j = 1; j <= i; j ++) {
			for (auto [l, r] : ins[j]) upd[r].push_back(l);
			int lft = -1, lst = -1; 
			for (int k : col[j][i]) {
				if (lst != k - 1) {
					if (lft != -1) Ans += query(n) - query(lft - 1);
					lft = k;
				} lst = k; for (int x : upd[k]) add(x, 1);
			}
			if (lft != -1) Ans += query(n) - query(lft - 1);
			clear(); 
		}
		for (auto [l, r] : vec) ins[lst[l][r]].clear();
		for (int j = 1; j <= n; j ++) upd[j].clear();
	} cout << Ans << "\n";
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...