省选-数据结构-双半群模型 · Zhl2010 第二博客

循环不变式

例如线段树区修区查的正确性依赖于它计算答案时的：

$sum_x+(r-l+1)\times \sum_{y 是 x 的祖先} tag_y$

我们把类似的“某个算法保持进行完操作后满足的等式”统称为循环不变式。

双半群模型

标记和信息。

标记需要复合封闭，也就是可以一堆 tag 套起来。
信息需要可合并。

简单总结

我们数据结构分两种，一是单纯存数据，二是存一个函数。

P2572 [SCOI2010] 序列操作

P2572 [SCOI2010] 序列操作。

这道题设计 $tag$ 表示是否全 $0/1$ ，是否反转。

然后信息就是 $0/1$ 个数，最长连续长度，左边最长，右边最长。

注意覆盖的优先级很高。

P4247 [清华集训 2012] 序列操作

P4247 [清华集训 2012] 序列操作。

信息： $1$ 到 $20$ 选数的答案。
标记：区间加，取相反数。

然后我们需要推循环不变式。

思路

区间加操作

执行区间加 $x$ （即每个数变为 $a_i+x$ ）后，新的 $g_k$ 满足：

g_k = (a_1+x)\times (a_2+x)\times \cdots (a_k+x)

g_k = \sum_{j=0}^{k} f_j \cdot \binom{len-j}{\,k-j\,} \cdot x^{\,k-j}

区间取反操作

g_k = (-1)^k \cdot f_k

上传

x_k = \sum_{i=0}^{k} l_i \cdot r_{k-i}

P8969 幻梦 | Dream with Dynamic

P8969 幻梦 | Dream with Dynamic。

看到 popcount 这种东西，自然会想到做完之后，所有数都会在一个范围之内了。

这道题 $popcount(x) \le 60$ 。

我们只需要对做了 popcount 的区间进行处理，因为做完之后，数的种数就在 $60$ 以内了。

信息：如果有 popcount，需要记录 popcount 后每一个数进入之后出去的值。
标记：是否又 popcount，还有加操作的 add。

这道题相当于就是维护一个复合函数去了，因为这个标记与信息可以凑出一个函数，只需要输入 $a_i$ 就行了。

青蛙思直线

QOJ - 5174 青蛙思直线。

也是相当于线段树维护函数。代码毒瘤，不想写了。

扫描线

感觉扫面线的关键就是离线扫描一维+数据结构维护一维。

数据结构可以是各种东西，最常见的是线段树。

离线思想总结。

P5490 【模板】扫描线 & 矩形面积并

P5490 【模板】扫描线 & 矩形面积并。

我们按照 $y$ 轴从下往上扫，我们存出每个矩形的上下界，就会发现这些之间，连续的一段被覆盖的 $x$ 的位置都是相同的，所以我们只需要维护这一段 $x$ 的长度，再乘上 $y$ 就是面积了。

“在所有操作之后输出结果”是经典的离线问题，有这句话几乎意味着在线不可做，我们需要离线下来，扫描线先就是一大思路。

P7880 [Ynoi2006] rldcot

P7880 [Ynoi2006] rldcot。

感觉这又是一种不完全一样的扫描线思路，按 $l$ 排序，从右往左添加 $[l,r]$ ，对于每一个 $l$ 维护出最小的 $r$ ，查询就对每个 $ql=l$ 查询这里面有多少个 $r$ 即可。

也就是二维的区间 $[l,r]$ 也可以扫描一维。

思路

先处理出要用的点对，我们可以用树上启发式合并存。因为对于每一个 $x$ ，只需要找到前驱和后继的点对，只有这样的点对是有效的，因为包含别人的相同颜色点对一定没别人优。

然后按 $l$ 排序，从右往左添加 $[l,r]$ ，对于每一个 $l$ 维护出最小的 $r$ ，查询就对每个 $ql=l$ 查询这里面有多少个 $r$ 即可。

注意需要防止未定义行为：

C++

s[x].insert(0);
s[x].insert(n+1);

CF526F Pudding Monsters

CF526F Pudding Monsters。

P8600 [蓝桥杯 2013 省 B] 连号区间数。

连续段计数问题。需要配合单调栈。

思路

我们需要找出一段，保证 $Max-Min=r-l+1$ 。转化一下式子就是 $Max-Min-len=-1$ 。

然后，我们使用扫描线的思路，扫描 $x$ 维。我们移动、固定 $r$ ，然后维护 $l$ 有多少个 $-1$ 。

怎么维护？我们发现，移动 $r$ 时， $len$ 都会 $-1$ ，直接维护就行了，然后我们可以用两个单调栈维护出哪些区间的 $Min$ 和 $Max$ 会变化。

然后我们只需要一个区间修改区间查询值为 $-1$ 的线段树。但是我们发现做不到。于是有一个比较巧妙的做法就是 $-1$ 一定是最小值，并且每个区间都有，我们只需要维护最小值和其个数就行了。

P8518 [IOI 2021] 分糖果

P8518 [IOI 2021] 分糖果。

这道题是对一个数的值设定了上下限。

题解里面总结出了一种思想：将序列维度和时间维度交换，也就是我们扫描序列，维护时间这个维度的信息。有点扫描线的意思了。

这道题就是扫描糖果，我们知道的是某个区间有糖果，所以扫描线 $l$ 加入， $r+1$ 删除。然后时间就是我们要维护的用来查询的东西。

所以很多时候需要将时间这个维度放入考虑范围，相当于一维的题目看成二维。

思路

我们一点一点分析问题。先只看下界，我们发现，我们只需要找每次对 $0$ 取 $max$ 的最后一个点，也就是前缀和最小的时候，这时候，值一定不会再下降了，不会再对 $0$ 取 $max$ 了。于是可以线段树上二分找最小前缀和。

再加上上界，就会发现，这是 $max$ 和 $min$ 交替的过程。我们只需要找出最后一次取 $min/max$ 就行了。

我们发现性质： $min$ 与 $max$ 区间之间的操作改变值的绝对值一定比 $c$ 大，于是我们可以线段树二分找到最后一个交替的位置。

这道题就是扫描糖果，我们知道的是某个区间有糖果，所以扫描线 $l$ 加入， $r+1$ 删除。然后时间就是我们要维护的，用于进行线段树二分。

注意合并时从右往左。

P5526 [Ynoi2012] 惊惶的 SCOI2016

P5526 [Ynoi2012] 惊惶的 SCOI2016。
CF1172E Nauuo and ODT。

这道题也用到了这种离线的思想，就是当前修改会对后面的产生多大的影响，差分下来。

不知道放这里合不合适。

思路

给你一棵 $n$ 个节点的树，每个点有个颜色，有 $m$ 次修改，每次修改需要输出树上所有有向简单路径的颜色数的和。

首先，我们需要求对于每个颜色有多少条路径包含了。

神奇正难则反：求不包含这个颜色的路径数。然后此时的答案就是选取不包含这个颜色的节点，所有连通块大小的平方和。

然后就想办法用 LCT 维护颜色数。

我们只需要离线下来处理每一个颜色即可。然后这就变成了一个双色问题，题解中说了一道 Qtree6，就是双色问题的基础。

利用性质对于这个颜色，其余颜色不管怎么变都不会影响。我们只需要对于每个颜色，处理一遍就行了。