菜王的 blog

题单

题意

link

给定序列 $a$，并且给出两种操作：

• 1 x y v：将所有 $a_i$ 的值加上 $v$，其中 $i\equiv y\pmod {2^x}$。
• 2 x y：询问所有 $a_i$ 的和，其中 $i\equiv y\pmod {2^ x}$。

题解

一道结合了 Trie 和 Lazytag 的好题。

我们考虑修改和查询涉及到的下标。

发现，一个数对 $2^x$ 取模，就相当于取这个数的二进制表示的右 $x$ 位。于是，所有的满足 $i \equiv y\pmod {2^x}$ 的 $i$ 都有一个长度为 $x$ 的后缀 $y$。

所以，我们考虑把所有的下标的二进制形式倒序插入一颗 01-Trie，那么每次修改就是子树加，查询就是子树查询。

在 01-Trie 中维护 $sum$ 和 $siz$ 即可。

题意

link

给定 $n$ 天的气温 $T_i$，设第 $i$ 天温度为 $P$，则第 $i+1$ 天的温度为：

• $P + 1 \ (P < T_i)$

• $P - 1 \ (P > T_i)$

• $P \ (P = T_i)$

对第 $i$ 天有 $k_i$ 个询问，问若第 $0$ 天的温度为 $x$，那么第 $i$ 天的温度是多少。

强制在线。

题解

比较小清新的数据结构。

考虑直接用一棵动态开点线段树维护初始温度在 $[l, r]$ 之间的答案最小值和最大值。

再考虑增加气温时该如何维护。

当我们在 $u$ 节点时：

• $\max_u < t_i$ 这时可以直接将 $u$ 区间加 $1$。

• $\min_u > t_i$ 这时可以直接将 $u$ 区间减 $1$。

• $\min_u = t_i = \max_u$ 这时可以直接返回。

• 否则，递归进入两棵子树。

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

题意

link

给一个长度为 $n$ 的序列 $a$，有 $q$ 次询问，每次询问一个区间内任意一个出现 $1$ 次的数，如果没有，输出 $-1$。

题解

比较小清新的数据结构。

首先考虑限制条件的本质。

设数组 $pre_i$ 为使得 $j < i$ 且 $a_j = a_i$ 的最大的 $j$，且当前左右端点分别为 $l, r$，那么一个数 $a_i$ 在 $[l, r]$ 中只出现了一次当且仅当：

• 它是 $[1, r]$ 中最后一个 $a_i$。

• $pre_i < l$。

那么，在 $[l, r]$ 中寻找的 $a_i$ 在 $[1, r]$ 中最后一次出现的，且 $pre_i$ 最小的 $i$，如果这个 $i$ 不是解，必定没有解；否则输出 $a_i$ 即可。

维护在 $[1, r]$ 中最后一次出现且 $pre_i$ 最小的 $i$ 可以用线段树，但是 $r$ 不固定，怎么办？有两种解决方案：

1. 主席树。
2. 将询问离线下来按照 $r$ 排序，只需要普通的线段树。

时间复杂度为 $O(n \log n)$。莫队垃圾

题意

link

给出一个 $1$ 到 $n$ 的排列，现在对这个排列进行 $m$ 次局部排序，排序分为两种，将区间 $[l, r]$ 的数字升序或降序排序。

最后询问位置 $p$ 上的值。

题解

神仙二分 + 线段树。

我们考虑二分位置 $p$ 的值。怎么 check 呢？

我们考虑 check $a_p \ge x$。

构造一个 01 序列 $b$，$\forall i \in [1, n], b_i = [a_i \ge x]$。

然后在 01 序列 $b$ 上执行排序操作，最后如果 $b_p = 1$ 则 $a_p \ge x$。

为什么这样是对的呢？因为在 $b$ 序列中，元素的相对大小顺序没有改变，大于等于 $x$ 的元素还是大于小于 $x$ 的元素。

排序操作可以用支持区间修改的线段树实现。

题意

link

给定 $n$ 件物品，第 $i$ 件物品有如下信息：

• 卖出去可以得到 $p_i$ 的收益。

• 过期时间为 $d_i$，过了过期时间就不能再卖出去。

卖掉一件物品要用 $1$ 的时间，求最大收益。

题解

首先，我们可以想到一个贪心思路：把物品按照 $p_i$ 从大到小排序，优先卖出 $p_i$ 大的物品，且每一个物品的卖出时间都尽量靠后。

所以对于每一个位置，我们支持占用一个位置，和求出某个位置前面第一个空闲的位置。

我们考虑使用并查集维护。如果占用了位置 $p$，那么把位置 $p$ 合并到位置 $p - 1$ 上，查询时查询某个位置的根节点。

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

题意

link

给一个长度为 $n$ 的字符串，$m$ 次询问，每次询问一个连续子串是否可以重排成一个回文串。

题解

一道很不错的莫队题。

显然，一个区间重排后可以成为一个回文串当且仅当其中有 $0$ 或 $1$ 个字符出现了奇数次。

我们只关心字符出现次数的奇偶性，所以我们可以把字符串所有的前缀状压成一个数，查询时直接异或即可。

添加 / 删除时枚举是哪一种字符出现了奇数次，时间复杂度为 $O(|\Sigma|n \sqrt n)$。

题意

link

给一个长度为 $n$ 的序列 $a$，$m$ 次询问，每次询问区间众数。强制在线。

题解

首先可以把序列离散化。

然后发现答案只可能是在两个散块里的数，或者是整块段的众数。

整块段的众数可以 $O(n)$ 预处理，两个散块里的数最多是块长级别，预处理出每一种数出现的位置，在位置数组里二分查找即可解决散块的问题，可以做到单次查询 $O(b \log n)$。

经过亲测块长设 $40$ 比较优。

题意

link1

给你一个长度为 $n$ 的序列 $a$，$m$ 次询问，每次询问一个区间是否可以选出两个数它们的和 / 差 / 积为 $x$。

选出的这两个数可以是同一个位置的数。

link2

在上一题的基础上，每次询问一个区间是否可以选出两个数它们的商为 $x$。

题解

设 $w$ 为值域，使用两个 bitset 分别统计 $x$ 与 $w - x$ 有没有出现过，使用 << 与 >> 操作即可统计加和减操作。

而乘操作可以暴力枚举质因子，时间复杂度为 $O(\frac{nw}{64} + n \sqrt w)$。

对于除操作，我们考虑根号分治。

如果 $x \ge \sqrt{w}$，可以直接枚举 $i$，判断 $x$ 与 $ix$ 是否同时出现。

否则对于每一个 $x$ 计算答案，求出 $las_i$ 为 $i$ 在 $a$ 中最后出现的位置，$res_i$ 为满足在 $[l, i]$ 中同时出现 $y$ 与 $xy$ 或 $y$ 与 $\frac{y}{x}$ 的最大的 $l$。每一个询问检查是否满足 $res_r \le l$ 即可。设 $w$ 为值域，时间复杂度仍为 $O(\frac{nw}{64} + n \sqrt w)$。

题意

link

给一个长度为 $n$ 的序列，$m$ 次询问，每次查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod p$。（$p$ 在每个询问里不同）

题解

考虑计算每一个数的贡献。假设区间长度为 $l$，这个数在区间里出现了 $t$ 次，根据容斥原理（出现的次数减去不出现的次数），这个数的贡献就是 $2^l - 2^{l - t}$。

根据乘法分配律，相同的数可以一起乘，又因为同一区间内最多只有 $\sqrt n$ 种贡献，所以可以用一个双向链表来维护贡献为某个值的和，暴力计算。$2^k$ 用光速幂处理一下即可。

题意

link

给你一个长度为 $n$ 的序列 $a$。

回答 $q$ 个这样的询问：$a$ 的左端点在 $[l_1, r_1]$ 之间，右端点在 $[l_2, r_2]$ 之间的子区间的中位数的最大值。

保证 $l_1 < r_1 < l_2 < r_2$。强制在线。

题解

对于求中位数，有一个套路：二分中位数 $mid$，把所有 $\ge mid$ 的值设为 $1$，$< mid$ 的值设为 $-1$，如果区间和 $\ge 0$，那么 $mid$ 就可能成为区间里的中位数。

我们可以对于二分的每一个 $a$ 里的值开一棵对应的线段树，但是一棵线段树可以由之前的线段树修改而来，所以只需要一棵可持久化线段树即可。

但是区间不固定，所以我们应该尽可能让上式的值最大。容易发现，$[r_1 + 1, l_2 - 1]$ 是必选，而 $[l_1, r_1]$ 与 $[l_2, r_2]$ 分别取最大前缀和与最大后缀和，套用小白逛公园的做法即可。

题意

link

定义一个可重集的神秘数为最小的不能被这个集合的子集和表示的数。

给一个长度为 $n$ 的正整数序列 $a$，$m$ 次询问，每次询问由 $a_l,a_{l+1},\cdots,a_r$ 所组成的可重集合的神秘数。

题解

我们先思考暴力做法：设当前覆盖区间为 $[1, x]$，那么每一个 $\le x + 1$ 的项都对答案有贡献，设它们的总和为 $sum$，$ans \to ans + sum$；如果没有这样的项，$x + 1$ 就无法被组成，答案为 $x + 1$。

每一次查找可以用可持久化值域线段树优化至 $\log w$，而每一次增长后 $ans$ 至少翻倍，最多只能增长 $\log \sum a_i$ 次，所以时间复杂度为 $O(n \log n \log \sum a_i)$。

题意

link

你需要维护一个长度为 $n$ 的 01 序列。

你会接到 $q$ 条信息：

1. 告诉你一个区间的按位或值。
2. 问你序列中一个数的值。如果不能确定，输出 N/A。

保证信息正确。

题解

我们称按位或为 $x$ 的区间为“$x$ 区间”。

可以发现一些性质：$0$ 区间里每个数都是 $0$；$1$ 区间至少有一个数为 $1$。

能确定一个数为 $0$，当且仅当一个 $0$ 区间包含这个数；能确定一个数为 $1$，当且仅当一个 $1$ 区间包含这个数，且该区间内其余的数均被确定为 $0$。所以，一个 $1$ 区间至多能确定一个数为 $1$。

我们考虑把操作序列离线下来，这样我们就可以算出每个位置得知所有信息后的值。然后求出每个位置能确定的最早时间即可。

具体来讲，我们记录所有修改操作和询问操作的时间，然后确定每个数最早被确定为 $0$ 的时间。

然后对于每个 $1$ 区间，如果该区间内有 $> 1$ 个数到最后也未被确定为 $0$，则不考虑该区间；否则，设唯一的最后也未被确定为 $0$ 的数在位置 $p$，该区间内最后一个被确定为 $0$ 的数在时刻 $lst$ 被确定为 $0$，收到该区间的时刻为 $t$，那么位置 $p$ 在 $\max(lst, t)$ 时刻可以被该区间确定为 $1$，一个位置能被确定为 $1$ 的时刻显然是最先确定该位置的 $1$ 区间确定该位置的时刻。

所有任务都可以用一棵线段树完成，时间复杂度为 $O(n \log n)$。

题意

link

有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一棵树是合法的，当且仅当树上所有简单路径上点权的异或和都不为 $0$。

你可以对点权进行修改，可以改成任意正整数，问最少修改多少次才能让这棵树合法。

题解

启发式合并。

首先，对于每一个 $u$，我们可以预处理出 $1$ 到 $u$ 的简单路径上点权的异或和，记为 $d_u$。然后 $u$ 到 $v$ 的简单路径上点权的异或和显然就是 $d_u \oplus d_v \oplus a_{\operatorname{lca}(u, v)}$，我们考虑枚举 $\operatorname{lca}(u, v)$ 来修改 $a_{\operatorname{lca}(u, v)}$。

我们还发现，一个节点如果要修改的话，一定会改成远大于值域的一个极大值，使经过这个点的每一条简单路径的异或和都不为 $0$。

所以我们考虑这样的一个贪心：对于每一个节点开一个 set 维护以这个节点为根的子树里所有节点 $u$ 的 $d_u$，特别的，如果这个节点修改成了极大值，这个节点对应的 set 为空。然后对于整棵树 dfs 一遍，假设当前在节点 $u$，递归进入每一个儿子 $v$，回溯时将 $v$ 的 set 使用启发式合并动态并入 $u$ 的 set，并在插入过程中动态查找当前 $u$ 的 set 中是否有两个数异或值为 $a_u$。如果有，$a_u$ 必须修改成极大值，将 set 清空即可。至于清空的原因，是因为 $u$ 的子树里任何一个点都不可能与外面一个点构成一条异或和为 $0$ 的简单路径。

贪心正确性显然，时间复杂度为 $O(n \log^2 n)$。