「Pudding Monsters」Solution

简述题意

给定一个 $n\times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。

对于所有的 $1\le k\le n$，求有多少个 $k\times k$ 的子棋盘中恰好有 $k$ 个棋子，输出其总和。

• $n\le 3\times 10^5$。

思路

在某个 $k\times k$ 的子矩阵中，显然行是连续的，列也是连续的。并且，每行每列恰好只有一个棋子，即每一行都唯一对应着某一列，这都启发我们把二维平面压缩成一个排列，即令 $a[x]=y$。
那么 $k\times k$ 的子矩阵中有 $k$ 个 $1$ 就等价于 $a$ 中某段子序列的值是连续的，原题就转化为经典的 值域连续段个数 问题。

可能有点抽象，举个例子：
$a:[1,5,2,4,3]$，满足条件的子序列就有 $[1],[5],[2],[4],[3],[4,3],[2,4,3],[5,2,4,3][1,5,2,4,3]$，如果还觉得抽象可以把上述子序列还原成二维，可以加深理解。

然而，值域连续是很难刻画的，一般从最值入手，即如果某个子序列 $[l,r]$ 值域连续，其一定满足：

max ⁡ { a l , a l + 1 , . . . , a r − 1 , a r } − min ⁡ { a l , a l + 1 , . . . , a r − 1 , a r } = r − l \max\{a_l,a_{l+1},...,a_{r-1},a_r\} - \min\{a_l,a_{l+1},...,a_{r-1},a_r\}=r-l max{al​,al+1​,...,ar−1​,ar​}−min{al​,al+1​,...,ar−1​,ar​}=r−l

还有一个条件是 $[l,r]$ 中每一个数仅出现一次，然而这个条件在此题中是天然满足的。

因此，我们只需要知道有哪些子序列的最大值减去最小值等于序列长度即可，对于序列计数问题，一般都是固定某个端点进行统计，而值域连续段就是通过固定右端点实现的。

不妨令现在的右端点为 $rpos$，并用一颗线段树维护左端点，具体地，某个节点 $[l,r]$ 表示的就是对于 $\forall i\in [l,r]，[i,rpos]$ 中 $\max -\min +i-rpos$ 的值，然而，我们是难以统计上述式子的所有取值的，因此引入一个性质：

• 对于某个子序列 $[l,r]$，一定有 $\max -\min +l-r\ge 0$。

因此，对于当前右端点，由于 $[rpos,rpos]$ 上述式子的值显然为 $0$，所以 $rpos$ 结尾的所有子序列中上述式子的最小值一定是 $0$。因此，我们只需要维护线段树上的最小值以及最小值出现的次数，就是 $\max -\min +l-r=0$ 的个数。

考虑如何维护线段树。

• 对于式子中的 $+l$，直接将线段树叶子节点（即左端点）的初值置为 $l$ 即可。
• 对于式子中的 $-r$，我们每次 $r\leftarrow r+1$ 时，给全局每一个位置减去 $1$ 即可。
• 而子序列最大值，最小值就用单调栈维护。以最大值为例，记单调栈为 $s$，栈顶为 $top$，如果 $a_{s_{top}}\le a_i$，那么就说明，对于 $j\in [s_{top-1}+1,s_{top}],[j,i]$ 这些子序列，其的最大值由 $a_{s_{top}}$ 变为了 $a_i$，那么我们给区间 $[s_{top-1}+1,s_{top}]$ 加上一个 $a_i-a_{s_{top}}$ 即可，然后 $top\leftarrow top-1$ 继续维护单调栈即可。最小值同理，不过区间加变为区间减了。

代码

上述做法就是值域连续段的经典解法，算是一个 $\text{trick}$ 吧 (((

#include<bits/stdc++.h>
#define int long long
#define pii pair<int , int>
using namespace std;
const int MAXN = 3e5 + 5;
namespace Segment{
	struct tree{
		int l , r , add , Min , cnt;
	}tree[MAXN << 3];
	void pushup(int p) {
		tree[p].Min = min(tree[p << 1].Min , tree[p << 1 | 1].Min) , tree[p].cnt = 0;
		if (tree[p << 1].Min == tree[p].Min) tree[p].cnt += tree[p << 1].cnt;
		if (tree[p << 1 | 1].Min == tree[p].Min) tree[p].cnt += tree[p << 1 | 1].cnt;
	}
	void pushdown(int p) {
		tree[p << 1].Min += tree[p].add , tree[p << 1 | 1].Min += tree[p].add;
		tree[p << 1].add += tree[p].add , tree[p << 1 | 1].add += tree[p].add;
		tree[p].add = 0;
	}
	void build(int p , int l , int r) {
		tree[p].l = l , tree[p].r = r , tree[p].add = 0;
		if (l == r){
			tree[p].Min = l , tree[p].cnt = 1;
			return;
		}
		int mid = l + r >> 1;
		build(p << 1 , l , mid) , build(p << 1 | 1 , mid + 1 , r);
		pushup(p);
	}
	void update(int p , int l , int r , int v) {
		if (tree[p].l >= l && tree[p].r <= r) {
			tree[p].add += v , tree[p].Min += v;
			return;
		}
		pushdown(p);
		int mid = tree[p].l + tree[p].r >> 1;
		if (l <= mid) update(p << 1 , l , r , v);
		if (r > mid) update(p << 1 | 1 , l , r , v);
		pushup(p);
	}
	pii query(int p , int l , int r) {
		if (tree[p].l >= l && tree[p].r <= r) return make_pair(tree[p].Min , tree[p].cnt);
		pushdown(p);
		int mid = tree[p].l + tree[p].r >> 1;
		pii tmp1 , tmp2;
		tmp1.first = tmp2.first = 1e9;
		if (l <= mid) tmp1 = query(p << 1 , l , r);
		if (r > mid) tmp2 = query(p << 1 | 1 , l , r);
		if (tmp1.first < tmp2.first) return tmp1;
		if (tmp1.first > tmp2.first) return tmp2;
		return make_pair(tmp1.first , tmp1.second + tmp2.second);
	}
}
using namespace Segment;
int n , a[MAXN] , s1[MAXN] , top1 , s2[MAXN] , top2 , ans;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr) , cout.tie(nullptr);
	cin >> n;
	for (int i = 1 , x , y ; i <= n ; i ++) {
		cin >> x >> y;
		a[x] = y;
	}
	build(1 , 1 , n);
	for (int i = 1 ; i <= n ; i ++) {
		update(1 , 1 , n , -1);
		while (top1 && a[s1[top1]] <= a[i]) update(1 , s1[top1 - 1] + 1 , s1[top1] , a[i] - a[s1[top1]]) , top1 --;
		s1[++ top1] = i;
		while (top2 && a[s2[top2]] >= a[i]) update(1 , s2[top2 - 1] + 1 , s2[top2] , a[s2[top2]] - a[i]) , top2 --;
		s2[++ top2] = i;
		ans += query(1 , 1 , i).second;
	}
	cout << ans;
	return 0;
}