【题解】YACS 棋盘 & CF526F Pudding Monsters

YACS 棋盘/ CF526F Pudding Monsters

有一个 $n \times n$ 的正方形，每行每列都恰好有一个 $1$，计算有多少子正方形满足每行每列恰好有一个 $1$。
$n \le 10^5$

$\texttt{Solution}$

考虑把两维的问题降维，首先把所有点按照横坐标排序，然后把纵坐标依次放在数组 $s$ 中。则对于 $s$ 中的一个区间，代表的点的 $x$ 连续，不难发现当这段区间的 $y$ 重排后恰好也是连续的一段，则这个区间代表的正方形满足条件。

则将问题转化为：

给定一个长度为 $n$ 的排列，计算有多少区间重排后值域上是连续的一段。

考虑对于区间 $[l,r]$，令 $max = max\{s[l],...,s[r]\},min = min\{s[l],...,s[r]\}$，则该区间合法当且仅当 $max - min = r - l$，移项得：$l + max - min - r = 0$，又显然 $max - min \ge r - l$，即 $l + max - min - r \ge 0$，考虑在线段树上维护这个值，则只需知道最小值和最小值的出现次数即可。

套路地考虑在右端点右移的过程中，每一个左端点的情况。首先每次右移一次右端点到 $i$，则通过使所有 $1$ ~ $ i - 1$ 的值 $-1$，模拟右端点 $+1$ 的过程。然后来处理 $max,min$ 的变化情况。

考虑 $max$ 的情况，用一个单调栈维护每个极大值出现的位置，则显然单调栈中元素单调减，不难发现如果令栈顶下标为 $i$，栈中第二个元素下标为 $j$，则 $s[i]$ 管辖的范围是 $j + 1$ ~ $i$。每当加入一个新值，则从栈顶开始弹出一些小于他的值，同时修改这个被弹出的值管辖的线段树的区间。

$min$ 同理。

每右移一次右端点，则查询一次 $1$ 到这个位置，出现了多少个 $0$，即可统计有多少贡献。

复杂度 $O(n\log n)$