Data Structures.

[NOI2021] 密码箱

根据题意容易得出，

下文为了方便，令。

由于是分数的形式，不妨设。

于是有

即

可以证明，永远互质，因此不需要约分。

这一递推过程可以通过矩阵乘法实现。
$$

\cdot

$$
再分析两种操作。

`W` 操作相当于添加矩阵
$$

\cdot

$$
接下来考虑 E 操作。

若末尾两数为，则按题意变换为，按另一种方式变换为。

带入计算可以发现，两种方式所得结果完全相同。

于是该操作相当于添加矩阵
$$

\cdot

\cdot

$$
修改操作形如添加操作、区间 FILIP 和区间 REVERSE。平衡树维护四种状态下的乘积即可。

注意矩阵乘法运算顺序。

[JOISC2020] 星座 3

比较直接的做法是笛卡尔树套线段树合并。但还有更简单的做法。

尝试贪心。先按行从小到大扫描。下文中的冲突均指与下方星星的冲突。

假设已经得出了前行的局部最优解，准备插入位于第行的一颗星星。

显然有两种决策。

不选。产生代价。
选。此时所有已经选了但是会产生冲突的星星不能选，产生若干代价。

考虑如何维护冲突。

对于星星，会与其产生冲突的星星（不妨设）满足

会被影响的落在一个区间内。可以用并查集维护开区间的左右端点。

对于冲突点点权和，需要支持区间加、单点查询，可以使用树状数组维护。

还有这应该不是反悔贪心……树状数组修改时减去一个值表示冲突点不再被选中，不是所谓的反悔。

[CQOI2015]任务查询系统

离线怎么做？离线是不是，按查询点排序，加点，加点，加点。然后线段树查询。

更具体地，权值线段树维护每个权值有几个、区间权值之和。把修改差分一下，线段树上二分顺便求和即可。

在线做法直接换主席树就行了。

CF1767F Two Subtrees

先把树拍到 dfs 序上，然后相当于求两个区间加起来的众数。

区间众数经典做法：值域分块，莫队。

这一题相当于两个莫队，四个指针。

复杂度可能高于普通莫队。不会证。

[HNOI2016]序列

套路地算贡献。

设区间内最大值位置为，则所有跨过的区间最小值已经确定。贡献为。

接下来尝试确定与的贡献。

记表示左侧第一个小于的位置，表示左端点在、右端点在的贡献。那么显然有。

那么对于区间满足，左端点在、右端点为的贡献即为。对于所有之间的左端点，之间的最小值一定等于之间的最小值也就是，可以直接减去。

于是右半部分的贡献即为。单调栈预处理再做一个前缀和就好了。

左半部分同理。

[NOIP2022] 比赛

这不比棋局好写多了？

考虑离线，扫描线维护右端点为的询问。同时维护两序列的单调栈。

尝试计算以为右端点的区间的贡献。设两单调栈栈顶分别为，则有

对于，序列在上的最小值为。
对于，序列在上的最小值为。
其余部分最小值不变。

考虑使用线段树维护的最小值及其乘积。的答案即为线段树上对应区间的乘积历史版本和。

记。相当于支持区间推平操作和区间加。

需要维护

。
及其历史版本和。

维护以下懒标记：

区间赋值标记。
。

注意细节。

[省选联考 2021 A/B 卷] 宝石

从下往上跳很好处理，每次跳到最近的下一个位置。这个过程可以倍增优化。

考虑将询问离线。在线地跳完的部分，设正在“等待”的宝石为，则在上打上的标记，同时在打上的终止标记。

自上而下 dfs，对于每个点，需要支持以下操作：

对于所有加入标记，将放入容器。
将容器内的元素放入下一个容器。
对于所有终止标记，查询所在容器。
退出时撤回所有操作。

可以使用可撤销并查集维护。

数据结构