【题解】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)$

添加新评论