数据结构练习

Posted on | In

数据结构练习，持续更新中。

LOJ2492.「BJOI2018」二进制

题意

维护一个长为 $n$ 的 $01$ 串，维护：

  • 单点修改；
  • 给定 $[L,R]$，统计其满足“重排列后能够成为二进制下 $(11)_2$ 的倍数”的子区间 $[l,r]$ 个数。

$n,q\le 10^5$，TL 2s。

link: https://loj.ac/p/2492

思路

首先观察条件的等价命题。

注意到是否成立仅与区间内 $1$ 的个数 $s_1$ 与 $0$ 的个数 $s_0$ 有关：

  • 如果 $s_1$ 为偶数，显然可以构造 $(0\cdots01\cdots1)_2$；

  • 否则若 $s_1=1$ 则显然不行，否则：

    • 若 $s_0\ge2$，则可构造 $(0\cdots01\cdots110101)_2$；
    • 否则若 $s_0=0$ 显然不行，若 $s_0=1$ 则因为长为 $l$ 的 $(1\cdots 1)_2\equiv0\pmod3$，不可能通过置一位为 $0$ 来得到 $3$ 的倍数。

    考虑不成立的充要条件：

  • $s_1=1$；

  • $2\nmid s_1$ 且 $s_0\le 1$。

考虑用线段树维护 $01$ 段：维护每个点所在段的左右端点。

接着考虑用线段树维护 $[L,R]$​ 中满足以上条件的区间个数。

假设我们将 $[L,R]$ 分割为 $[L,mid]$ 与 $[mid+1,R]$ 两部分，那么只需考虑跨过 $mid+0.5$ 的区间个数即可。

第一个条件

先考虑 $1$ 在左儿子的情况：右儿子提供一个全 $0$ 前缀，左儿子提供一个恰包含一个 $1$ 的后缀。

维护每个区间最长全 $0$ 后缀的长度 $R{01}$ 及最长仅含一个 $1$ 的后缀长度 $R{11}$，以及最长全 $0$ 前缀的长度 $L{01}$，最长仅含一个 $1$ 的前缀 $L{11}$。

$1$ 在左儿子的答案为 $rs.L{01}\times (ls.R{11}-ls.R_{01})$，右儿子同理。

第二个条件

对于 $s0=0$，直接维护最长全 $1$ 前缀/后缀 $L{00}$/$R{00}$ 即可。分别讨论左儿子和右儿子谁贡献奇数，答案为 $\lceil ls.R{00}/2\rceil\lfloor rs.L{00}/2\rfloor+\lfloor ls.R{00}/2\rfloor\lceil rs.R_{00}/2\rceil$.

对于 $s0=1$，则同理维护最长仅含一个 $0$ 前缀/后缀 $L{10}$/$R{10}$。若 $ls.R{00}$ 为偶数，则删去左儿子的 $R_{00}$ 后缀后可类似上式计算；否则也类似上式，但两项的取整方向相同。

同时满足两个条件

仅有三个串：$01$、$10$、$1$。

$1$ 仅会在叶节点出现，叶节点考虑是平凡的。

剩下的两个仅会在合并时出现，且仅有一种可能：$a{mid}\ne a{mid+1}$。特判 $-1$ 即可。

维护 $L$、$R$

大多数情况下，$L\gets ls.L$，不过也有例外，譬如左儿子的 $0$/$1$ 过少（少于 $2$），那么需要开始用 $rs.L$。如何判断左儿子 $0$/$1$ 是否过少？一个简单的方法是多维护 $cnt_{0/1}$。

时间复杂度 $O(m\log n)$。

LOJ3325. 「SNOI2020」区间和

题意

给定一个长为 $n$ 的整数序列，维护两种操作：

  • 区间 $<k$ 的数设为 $k$；
  • 求一个区间内的最大子段和。

$n\le 10^5$，$q\le 2\times 10^5$，$|a_i|,|k|\le 10^9$，TL 3s。

link: https://loj.ac/p/3325

思路

对于修改，看上去要用 Segment Tree Beats 维护。

查询根据经典套路，维护每个结点的最大前缀和最大后缀。

我们知道 ST Beats 的思想是仅处理仅会修改最小值的区间，其他的暴力递归，不过增加最小值对答案的影响是什么呢？乍一看最大前缀的区间不会修改，但是仔细考虑后会发现：$[3,-10,2,-10]$，如果将 $-10$ 全部改为 $1$，那么最大前缀的右端点会右移。

观察后会发现，最大前缀后移是因为有些前缀修改前的和较小但其包含了许多的最小值，当最小值增加 $\Delta$ 时它的和的增量非常大。容易发现存在一个阈值 $\max\Delta$，当答案小于这个数的时候区间一定不会变动。

假设有一个前缀被我们认为是“可能的未来最大前缀”，设其和为 $s’$，包含最小值 $c’$ 次，而目前的和为 $s$，包含最小值 $c$ 次。容易知道，当 $s< s’+(c’-c)\Delta$ 时，“彼可取而代之”，否则不行。移项得到 $\Delta>\dfrac{s-s’}{c’-c}$。如果我们的阈值小于所有的 $\dfrac{s-s’}{c’-c}$，那就一定不会导致区间的修改。

问题是，有可能存在很多的这样区间。考虑交给左右儿子分别处理。如果先令 $\max\Delta\gets\min{\max\Delta_l,\max\Delta_r}$，那么不难发现，若 $\Delta<\max\Delta$，那么左右儿子的最大前缀区间都不会改变。此时的“可能未来最大前缀”就只有一个，就是当实际最大前缀是左儿子的最大前缀时的右儿子最大前缀加上左儿子的全部区间。（注意到若取代了，$c’$ 必然大于 $c$，因此区间只会右移）

还有一个小细节需要注意：如果有多个最大前缀区间可以选择，选择最长的。如果选择最短的可能会导致不断的右移导致复杂度错误。

于是我们需要额外维护每个结点的阈值、最大前（后）缀包含的最小值数目、最小值出现次数。

时间复杂度据说是 $O(n\log^2n+q\log n)$，但我不会证。

代码

link: https://loj.ac/s/1429985

CF1322E Median Mountain Range

题意

给定一个序列 $a_n$，可以对它进行如下操作（设操作后的序列为 $a_n’$）：

  • $a_n’=a_n$，$a_1’=a_1$；
  • $ai’=\operatorname{medium}{a{i-1},ai,a{i+1}},i\in[2,n-1]$，其中 $\operatorname{medium} S$ 表示 $S$ 的中位数。

可以证明无论初始序列为多少，对整个序列操作有限多次后一定将变为一个经过操作之后不变的序列。问最少需要多少次操作才能使初始序列变为这种序列，并给出最终序列。

$n\le 5\times 10^5$，TL 2s。

link: https://codeforces.com/problemset/problem/1322/E

思路

首先考虑 $01$ 序列怎么处理。容易知道，相邻的两项是永远不会改变的，因而改变的仅有 $1010101010\cdots$ 串。观察一个极大 $01$ 交替串，这样的串修改一次会将其除了两端以外的所有值翻转。因此最多操作次数为最长 $01$ 交替串长度减 $1$ 除以 $2$ 向下取整。

考虑将原序列转化为 $01$ 序列：钦定一个定值 $k$，$\ge k$ 的修为 $1$，$< k$ 的修为 $0$。容易知道，序列转化后再操作和操作后再转化得到的是同样的 $01$ 序列，于是这个转化是合理的。容易知道任何时刻序列中的数都一定在原序列中出现过，于是我们钦定的 $k$ 只需要在原序列中取即可。当转化后的 $01$ 序列趋于稳定，说明不会存在一个数从 $\ge k$ 变为 $< k$，也不会反过来变回去。原序列的操作次数就是所有的 $k$ 的次数的 $\max$。容易知道序列在任何时刻都不会有初始序列没有出现过的元素，因此 $k$ 的个数是 $O(n)$ 的。

考虑大到小枚举 $k$，每次会有若干个数从 $0$ 变为 $1$。使用 std::set 维护极大 $01$ 交替串，每次将一个 $0$ 修改为 $1$ 只会影响其周围的 $O(1)$ 个串（可以在 $O(\log n)$ 的时间内定位到这些串），修改区间是 $O(\log n)$ 的，而 $0\to 1$ 的次数为 $O(n)$ 的，所以时间复杂度是 $O(n\log n)$ 的。

如何求出最终序列？注意到一个位置在最终序列为 $x$ 的充要条件为其在以 $x$ 为定值构建的 $01$ 序列中最终为 $1$ 且在以 $x+1$ 为定值构建的 $01$ 序列中最终为 $0$。我们用 std::set 维护当前在序列中最终为 $0$ 的位置，每次更改极大 $01$ 交替串的时候会有 $O(1)$ 个区间的最终答案升为 $1$，在 std::set 中找到区间内的数删除并打标记即可。时间复杂度还是 $O(n\log n)$ 的。

这道题放在数据结构练习里是因为有一个复杂的线段树实现。

事实上，还有一个 $O(n)$ 的做法，详见 https://codeforces.com/blog/entry/74148?#comment-587403。

UOJ612「JOISC 2021」Day1 フードコート | Food Court | 饮食区

题意

有 $n$ 个队列，请维护以下三种操作：

  • 将编号在 $[l,r]$ 内的队列全部 push $k$ 个 $c$。
  • 将编号在 $[l,r]$ 内的队列全部 pop $k$ 次，如果大小小于 $k$ 就清空。
  • 求队列从前往后第 $b$ 个数，或者判定如果大小小于 $b$。

$n,q,c\le 2.5\times10^5$，$b\le 10^{15}$，$k\le 10^9$，TL 1s。

link: https://uoj.ac/problem/612

思路

如果没有 pop 怎么处理？

先把询问离线下来，每个结点从小到大挂上一个询问值的 std::vector。建一棵线段树，初始每个位置的值为 vector 内的最小值。区间 push 相当于区间减，当一个区间被减成 $\le 0$ 的时候答案就是这次修改的 $c$。（当然，要判断这个修改与询问孰先孰后）处理完这个询问再把下一个询问挂在这个位置。

加上 pop 怎么处理？假设我们知道这个位置上总计 pop 了 $k$ 个数，那么判断有没有减成 $\le 0$ 的时候把下限减小一点即可。

怎么维护一个位置 pop 的个数？这是等于这个位置目前的长度减去其 push 的个数即可。

push 的个数就是区间加单点查，维护是平凡的；

目前的长度需要维护三种操作：

  • 区间加；
  • 区间减；
  • 区间对 $0$ 取 $\max$（被减完后需进行）。

直接 Segment Tree Beats。

时间复杂度 $O((n+q)\log n)$。