小数据结构

小数据结构题们，也有一些根号题。

Luogu 5072

给定一个序列，每次查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod\ p$。

数据范围：$1\leq n,m,a_i \leq 10^5$，$1\leq p\leq 10^9$，$1\leq l\leq r\leq n$。

---

考虑直接拆贡献，对于 $x$ 这个数，如果在 $[l, r]$ 中出现 $c$ 次，记区间长度为 $len$，那么它对答案的贡献即为 $x\times (2^{len}-2^{len-c})$，也就是所有子序列减去没有出现 $x$ 的子序列个数。

可以注意到相同的 $c$ 值可以直接记录 $x$ 的和来统一计算，又因为区间中不同 $c$ 的数量只有 $\sqrt n$ 种，可以用哈希表维护出现次数为 $c$ 的 $x$ 的和，哈希表会被卡常，可以采用链表。

计算 $2^x$ 可以直接光速幂。

时间复杂度 $O(n\sqrt{q}+q\sqrt n)$。

Luogu 3591

给定一棵 $n$ 个点的树，树上每条边的长度都为 $1$，第 $i$ 个点的权值为 $a_i$。

多次询问，每次询问给定 $x, y, k$，询问从 $x$ 出发，每步跳 $k$ 条边跳到 $y$ 所经过的权值和。保证每次行走的距离是 $k$ 的倍数。

数据范围：$n\le 50000$。

---

题面写的很裸，快把根号分治写脸上了。

对于 $k>B$，直接暴力跳 $k$ 级祖先即可，长剖可以做到 $O(\frac{n}{B})$，或者重剖倍增 $O(\frac{n}{B}\log n)$。

对于 $k\le B$，考虑离线下来 dfs 统一处理。先把路径拆成两段：$x\to \text{lca}, \text{lca}\to y$。 直接做一段的然后拼起来即可。对于每个 $k$ 都进行一遍 dfs，统计当前走到的点 $u$ 到根节点路径上 $dep\equiv a(\bmod k)$ 的点的权值和 $val_a$。 显然一段路径可以差分，就做完了。注意 $\text{lca}$ 处特判权值算两遍的情况。

时间复杂度 $O(q(B+\frac{n}{B}))$。

Luogu 5309

给定一个序列 $a$，支持两个操作：

• 给定 $x, y, z$，其中 $(y\le x)$，给所有 $k\bmod x=y$ 的 $a_k$ 加上 $z$。
• 求 $[l, r]$ 的区间和。

数据范围：$n,m\le 2\times 10^5$。

---

根号分治。

当 $x>B$ 时，暴力单点加，对于区间求和，可以采用 $O(1)$ 修改 $O(\sqrt n)$ 查询区间和的分块解决。

当 $x\le B$ 时，转化为前缀和 $[1, r]-[1,l-1]$。记 $f_{x, y}$ 为序列中下标 $\bmod x=y$ 的位置的加法标记，那么执行一次一操作就可以令 $f_{x,y}$ 加上 $z$。

考虑如何统计前缀和。先枚举 $x$，那么下标在 $\bmod x$ 意义下为：$1, 2, \cdots x-1, 0$ 这么一段的循环，显然会循环 $\left\lfloor\frac{len}{x}\right\rfloor$ 次，并且最后会有一段长度为 $len\bmod x$ 的前缀。那么我们对 $f_{x, i}$ 做一个前缀和即可，单次操作只需要修改 $O(B)$ 个值。

时间复杂度 $O(qB+q\frac{n}{B})$。

Luogu 7710

给你一棵边权为 $1$，且以 $1$ 为根的有根树，每个点有初始为 $0$ 的点权值，需要支持两种操作：

1 a x y z：把 $a$ 子树中所有与 $a$ 的距离模 $x$ 等于 $y$ 的节点权值加 $z$。

2 a：查询 $a$ 节点的权值。

数据范围：$n, m\le 3\times 10^5$。

---

先把树上问题搞到 dfn 序上，那么操作就可以变成：在 dfn 序的一段区间中，$dep\bmod x=y$ 的点都加上 $z$。

分块维护 dfn 序，散块暴力即可，对于整块应用根号分治。

当 $x>B$ 时，设 $f_{x, y}$ 为第 $y$ 个块内深度为 $x$ 的点的权值要加上多少，每次操作就是连续的块深度为 $x$ 的点都加上 $z$。每次操作枚举 $dep_a+y, dep_a+2y\cdots$ 然后差分即可。

当 $x\le B$ 时，设 $g_{i, x, y}$ 为第 $i$ 个块内 $dep\bmod x=y$ 的点的点权应该加上多少，这时就直接暴力每个块打标记即可。

询问的话对于 $x>B$ 就求前缀和，$x\le B$ 就直接枚举 $x$ 就行。

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

Luogu 4137

给定数列 $a$，多次询问区间 $\text{mex}$。

数据范围：$n,m \le 2\times 10^5$。

---

• Solution 1

  莫队+值域分块即可。有 $O(n\sqrt q)$ 次修改和 $q$ 次查询 $\text{mex}$，分块可以做到 $O(1)$ 修改和 $O(\sqrt n)$ 查询 $\text{mex}$。

• Solution 2

  在线段树上维护某个数出现过的最后一个位置，可以用主席树或者离线。然后线段树上二分最小的且出现位置小于 $l$ 的数。时间复杂度 $O(q\log n)$。

Luogu 5443

给定一张图，边有边权。$q$ 次操作，有两种操作：

• 将第 $x$ 条边边权改为 $y$。
• 从 $u$ 出发，只经过边权大于等于 $w$ 的边，能够走到多少个点。

数据范围：$n\le 5\times 10^4, q\le 10^5$。

---

考虑没有一操作时怎么做，可以把询问离线下来排序，回答询问前先把边权大于等于 $w$ 的边加入并查集，然后回答询问即可。

如果操作一比较少也是可以做的，也是离线下来排序，把大于等于 $w$ 且没有被询问改变的边加入并查集，回答询问时再看没有被加入并查集的边的边权为多少，如果小于 $w$ 就不加入。

这启示我们进行询问分块。每 $\sqrt q$ 次操作分一个块，每个块内只会涉及到 $O(\sqrt q)$ 个修改操作，那么每次回答询问时最多只需要扫 $\sqrt q$ 条边即可。

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

Luogu 5046

给你一个长为 $n$ 的排列，$m$ 次询问，每次查询一个区间的逆序对数，强制在线。

数据范围：$1\leq n,m\leq 10^5$。

---

先分块，考虑一次询问的答案会由哪些东西贡献。

贡献分为以下几种：

• 整块内部的逆序对数
• 两个散块分别和整块形成逆序对
• 两个散块内部的逆序对
• 两个散块之间的逆序对

对于散块内部，可以在每个块内部记录一个 $pre$ 数组和一个 $suf$ 数组，表示这个块内前/后 $i$ 个数会产生多少个逆序对，树状数组即可，$O(n\log n)$。

对于整块内部，设 $s_{l, r}$ 表示 $l\sim r$ 这些块内部有多少逆序对，有递推式 $s_{l, r}=s_{l, r-1}+s_{l+1, r}-s_{l+1,r-1}+contri(l, r)$。其中 $contri(l, r)$ 为 $l$ 块和 $r$ 块会产生多少逆序对，可以使用归并进行计算。时间复杂度 $O(n\sqrt n)$。

对于整块和散块产生逆序对，记 $cnt_{i, j}$ 为前 $j$ 个块有多少个数大于 $i$，开个桶然后做个前缀和就行。时间复杂度 $O(n\sqrt n)$。

散块和散块直接归并就行，复杂度 $O(\sqrt n)$。

但是发现这样常数太大了过不去。考虑减小常数。记 $f_{i, j}$ 为前 $i$ 个数会和第 $j$ 个块产生多少逆序对（考虑前后顺序），求法就是让第 $j$ 个块和所有数都归并一次，然后做个前缀和。

这样处理散块和整块的时候就只需要扫描一遍所有的整块，用前缀和一减就行。同时计算 $s_{l, r}$ 中的 $contri(l, r)$ 也不需要归并排序了。

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

Luogu 5047

给你一个长为 $n$ 的序列 $a$，$m$ 次询问，每次查询一个区间的逆序对数。

数据范围：$1\leq n,m \leq 10^5$，$0 \leq a_i \leq 10^9$。

---

没有强制在线的区间逆序对可以用莫队来做。每次加入/删除一个数就看它会和当前维护的数产生多少逆序对，树状数组维护是 $O(n\sqrt n\log n)$ 的。

发现莫队移动时会导致一个数多次加入，不好平衡复杂度，直接进行一个二次离线。可以发现每次询问都形如：查询区间 $[l, r]$ 中小于 $a_x$ 的数的个数。前缀和一下就变为查询 $[1, r]$ 中小于 $a_x$ 的数的个数，扫描线，使用 $O(\sqrt n)$ 修改 $O(1)$ 查询的分块即可。

但是这样空间复杂度为 $O(n\sqrt n)$，考虑优化空间。如果我们单拎出来 while(R < r) add(++ R); 这部分来看，可以发现在右端点移动时，左端点从来没有改变，右端点的移动是一段区间，那么可以把这堆询问直接挂到左端点。

这时我们的变化为：对于 $r\in [R, qr-1]$，$[1, r]$ 中小于 $a_{r+1}$ 的数之和减去 $[1, L-1]$ 中小于 $a_{r+1}$ 的数之和（$L, R$ 为莫队当前左右端点，$qr$ 为询问右端点）。前一部分可以预处理然后前缀和。后一部分左端点不变，右端点询问为一段区间，直接把这一段要回答的询问挂到左端点即可。

对于其他三种情况同理。

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

Luogu 5048

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

数据范围：$1\leq n,m,a_i \leq 5\times 10^5$。

---

分块，预处理 $f_{i, j}$ 表示第 $i$ 块到第 $j$ 块的众数出现次数，开个桶就能维护。再维护一下每个数出现的位置集合 $pos_x$。回答询问时先得到整块的众数出现次数 $res$，再考虑散块中是否有数能够成为众数。

以下是对于左散块而言的，如果这个数所在的集合中的位置加上 $res$ 的数（也就是让这个数再出现 $res$ 次的位置）仍在询问区间中，那就让 $res$ 加一即可。右散块同理。

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

Luogu 5356

一个长为 $n$ 的序列 $a$，需要支持 $m$ 次操作，操作有两种：

1. 查询区间 $[l,r]$ 的第 $k$ 小值。
2. 区间 $[l,r]$ 加上 $k$。

数据范围：$n, m\le 10^5$。

---

简单题。

分块，然后块内维护有序序列以及加法懒标记。可以发现有了块内有序序列之后查块内 $\text{rank}$ 只需要二分一下就行，这启示我们可以二分 $k$ 小值。

回答询问时二分 $k$ 小值，查 $\text{rank}$ 时整块内二分，散块暴力，单次询问复杂度为 $O((B+\frac{n}{B}\log n)\log n)$，比较难过。如果把散块事先归并，那么每次散块内查排名就可以一次二分完事。时间复杂度 $O(B+\frac{n}{B}\log^2 n)$。令 $B=\sqrt{n}\log n$，单次询问复杂度为 $O(\sqrt{n}\log n)$。

Luogu 4135

问题简述：给定 $n$ 个不大于 $c$ 的正整数 $a_1 \dots a_n$ 和 $m$ 组询问，每次问 $[l,r]$ 中有多少个数出现正偶数次。强制在线。

数据范围：$n,c, m\le 10^5$。

---

分块，预处理 $f_{l, r}$ 为第 $l$ 个块到第 $r$ 个块有多少个数出现正偶数次。再保存每个数出现的位置集合，这样就可以在 $O(\log n)$ 时间内求出在某段区间中这个数出现过多少次。散块就通过在询问区间中出现次数和在整块的出现次数的奇偶性分讨即可。

也可以记 $cnt_{i, j}$ 为前 $i$ 个块 $j$ 出现的次数，这样就可以 $O(1)$ 查询出现多少次了。

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

Luogu 4168

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

数据范围：$1\leq n,m,a_i \leq 40000$。

---

• Solution 1

  记 $cnt_{l, r, x}$ 为第 $l$ 个块到第 $r$ 个块中 $x$ 出现了多少次。散块暴力加，统计完后暴力减回去就行。这个东西好像可以叫做在线莫队？

  时间复杂度 $O(\frac{n^3}{B^2}+qB)$，令 $B=\sqrt[3]{\frac{n^3}{q}}$ 复杂度最优，为 $O(n^{\frac{5}{3}})$。

• Solution 2

  保存出现位置集合，然后二分即可得到出现次数来更新答案。时间复杂度最优 $O(n\sqrt {n\log n})$。

Luogu 4192

给定序列 $a$，$m$ 次操作，有两种操作：

• 区间加等差数列
• 区间求 $\max$

数据范围：$n, m\le 10^5$。

---

分块。块内保存这个块加的等差数列的首项 $c$ 和公差 $d$，那么一个位置上的数就可以表示为 $b_i+i\times d+c$。对于块内 $\max$ 是不需要考虑 $c$ 的，现在只需要考虑 $d$。

设最新的序列为 $a$，加上等差数列前的数列为 $b$，那么 $a_i=b_i+i\times d$，移项可得 $b_i=a_i-i\times d$，要让 $a_i$ 最大。发现这个形式形如 $y=kx+b$，每个数都可以看作 $(i, b_i)$ 这么一个点，用斜率为 $-d$ 的直线去带入，转化为让截距最大。

这样就好办了，块内维护凸包，每次二分求最大截距。散块就暴力下放标记重构即可。

时间复杂度 $O(q(B+\frac{n}{B}\log n))$。

CF464E

给定一张 $n$ 个点，$m$ 条边的无向图，每条边的边权为 $2^{x_i}$，求 $s$ 到 $t$ 的最短路，结果对 $10^9+7$ 取模。

数据范围：$n, m, x \leq 10^5$。

---

考虑 dijkstra 需要什么操作：比较 $dist$ 的大小、给 $dist$ 赋值。直接用主席树来维护 $dist$ 的二进制表示。注意到边权在二进制表示下都只有一个 $1$，那么一次加边权就相当于把一段 $1$ 赋值为 $0$，再把这些 $1$ 的更高位一个 $0$ 变为 $1$。线段树上二分可以找到这些位置。

比较大小可以类比字符串比较字典序，找 $lcp$ 然后比较 $lcp$ 下一位即可。对 $01$ 串进行哈希就可以做到。

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

CF526F

给定一个排列，求有多少区间满足区间极差等于区间长度。

数据范围：$n\le 3\times 10^5$。

---

扫描线。移动右端点，看有多少个左端点满足条件即可。条件为 $\text{max}-\text{min}+1=\text{len}$，移项可得 $\text{max}-\text{min}-\text{len}=-1$。维护区间中的 $\text{max}-\text{min}-\text{len}$，然后看有多少个点满足值为 $-1$ 即可。右端点移动时 $-\text{len}$ 是好维护的，区间减一即可。而 $\text{max}$ 和 $\text{min}$ 可以用单调栈来维护。

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

CF997E

给定一个排列，多次询问，求在区间 $[l, r]$ 中有多少区间满足区间极差等于区间长度。

数据范围：$n, m\le 1.2\times 10^5$。

---

和上一题一样，离线下来扫描线，维护 $\text{max}-\text{min}-\text{len}$。但是这次要查询的是在 $[l, r]$ 中每个位置都固定一次右端点然后查询 $[l, r]$ 中有多少满足条件的区间，复杂度过高。可以考虑维护历史和，维护每个位置出现过多少轮的 $-1$ 即可。

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

CF757G

一棵 $n$ 个点的树和一个排列 $p_i$，边有边权，支持两种操作：

• l r x，询问 $\sum\limits _{i=l}^{r} dis(p_i,x)$。
• x，交换 $p_x,p_{x+1}$。

数据范围：$n,q\leq 2\times 10^5$，强制在线。

---

先把询问拆成前缀和相减，然后要求的是 $\sum_{i=1}^{r}dis(p_i, x)$，把距离拆成 $dep$。可得要求的是：

$$\sum_{i=1}^rdep_{p_i}+r\times dep_{x}-2\sum_{i=1}^r dep_{lca(p_i,x)}$$

前两项是好维护的，唯一恶心的是第三项。不过做法日益普及：把 $p_{1\sim r}$ 到根的路径都加上对应的边权即可。强制在线就上主席树，然后树链剖分，标记永久化一下就行。

对于第二个操作，可以发现只会改变一颗主席树的值，暴力修改即可。

这题卡空间，所以可以定期重构主席树。

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

CF319E

有一个区间的集合，初始为空。当 $c<a<d$ 或 $c<b<d$ ，且 $(a,b),(c,d)$ 都在集合中时，你可以从区间 $(a,b)$ 移动到 $(c,d)$。你需要支持下面的操作：

• 加入一个新区间 $(x,y)$。保证加入的区间长度严格单调递增。

• 询问是否能从第 $a$ 个加入的区间移动到第 $b$ 个。

数据范围：$1\le n\le 10^5$。

---

如果我们把极大的两两互达的连通块称作一个区块，那么有如下引理：

• 区块应为嵌套类型，也就是大区块内包含一些小区块，小区块内包含一些小小区块。证明可以直接数学归纳，加入一个区间时把一些区块合并之后还是会满足条件。

用线段树来维护区块。在线段树的节点上维护有哪些区间完全覆盖了这个节点，那么把新加入的区间的左右端点所对应的这些位置都用并查集合并起来，这些就被归到一个区块内了，同时更新区块的左右端点即可。由于新区间的长度大于旧区间，也就是新区间不会被包含，因此上面的做法是正确的。

可达的条件有两个：在一个区块、起点所在的区块被终点所在的区块包含着。

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

Luogu 6623

给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$，定义 $x$ 的价值为：

$val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))$

其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$\oplus$ 表示异或运算。

求出 $\sum\limits_{i=1}^n val(i)$ 的结果。

数据范围：$1\leq n,v_i \leq 525010$，$1\leq p_i\leq n$。

---

用 trie 树来维护异或值。然后在 dfs 的过程中进行 trie 树合并，同时 trie 树上全局 $+1$ 即可。

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

Luogu 4198

给定序列 $a$，支持单点修改、查询前缀最值个数。

数据范围：$n\le 10^5$。

---

有一个比较抽象的做法：线段树上维护可持久化平衡树，然后 pushup 的时候在右子树中找到第一个大于左区间中 $\max$ 的位置，然后让这些数和左子树中的平衡树合并即可。

比较抽象，但好理解。

正常做法是每个节点维护一下自己代表的序列中前缀最值个数 $ans_p$，以及最大最小值。pushup 的时候分情况讨论：

• 右子树最小值大于左子树最大值，这时直接拼接起来就是该节点的 $ans$。
• 右子树最大值小于左子树最小值，右子树没贡献。
• 右子树和左子树的值域有交，这种情况是最恶心的，我们需要递归处理，找到这时右子树大于左子树最大值 $maxn$ 的部分的答案。
  • 如果当前节点的最小值大于 $maxn$ 就可以直接返回了
  • 左子树最大值小于 $maxn$，就递归右子树
  • 否则可以发现右子树的前缀最值都是大于 $maxn$ 的，答案可以直接算出来，为 $ans_p-ans_{lson}$，再去递归左子树

pushup 一共会递归 $\log n$ 层，因此复杂度为 $O(n\log^2n)$。

Luogu 5312

有一个长度为 $n$ 的数组 $A$。下标从 $1$ 开始标号。有 $m$ 个操作需要处理，操作有如下四种：

1. 在数组 $A$ 的末尾添加一个数 $x$。
2. 输出 $\sum_{i=l}^{r}A_i$。
3. 将数组 $A$ 中的每个数 $A_i$ 都改为 $A_i\oplus x$。（$\oplus$ 表示异或操作）。
4. 将数组 $A$ 从小到大排序。

数据范围：$n,m\le 10^5$。

---

显然 01trie 题。可以维护前半部分的有序数列以及后面无序数列。有序数列直接用 01trie 维护，无序序列可以做个前缀和来支持第二种操作。

至于全局异或可以打一个全局的标记。

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

Luogu 4117

长为 $n$ 的序列 $a$，有 $m$ 次操作

1. 把区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。
2. 查询区间 $[l,r]$ 中 $x$ 的出现次数。

数据范围：$n\le 10^6, m\le 5\times 10^5$。

---

分块，每个块内维护最大值，以及每个值所对应的下标集合。当块内最大值（记为 $maxn$）小于 $2x$ 时，可以让 $x+1\sim maxn$ 这些集合合并到 $1\sim x$ 中去，否则让 $1\sim x$ 合并到 $x+1\sim maxn$，同时打一个 $-x$ 的标记即可。散块就暴力重构，合并可以直接用并查集，就做完了。

这样空间是 $O(n\sqrt n)$ 的，注意到答案具有可加性，可以对每个块都扫一遍所有询问，然后加起来就行。

时间复杂度 $O(n\sqrt n\alpha(n))$。

Luogu 8496

对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。

一开始给定 $n$ 个长度不一的正整数序列，编号为 $1 \sim n$，初始序列可以为空。这 $n$ 个序列被视为存在，其他编号对应的序列视为不存在。

有 $q$ 次操作，操作有以下类型:

• $1 \ x \ y$：在 $x$ 号序列末尾插入数字 $y$。保证 $x$ 号序列存在，且 $1 \le x, y \le n + q$。
• $2 \ x$：删除 $x$ 号序列末尾的数字，保证 $x$ 号序列存在、非空，且 $1 \le x \le n + q$。
• $3 \ m \ x_1 \ x_2 \ x_m$：将 $x_1, x_2, \ldots, x_m$ 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 $-1$。数据保证对于任意 $1 \le i \le m$，$x_i$ 是一个仍然存在的序列，$1 \le x_i \le n + q$，且拼接得到的序列非空。
• $4 \ x_1 \ x_2 \ x_3$：新建一个编号为 $x_3$ 的序列，其为 $x_1$ 号序列后顺次添加 $x_2$ 号序列中数字得到的结果，然后删除 $x_1, x_2$ 对应的序列。此时序列 $x_3$ 视为存在，而序列 $x_1, x_2$ 被视为不存在，在后续操作中也不会被再次使用。保证 $1 \le x_1, x_2, x_3 \le n + q$、$x_1 \ne x_2$、序列 $x_1, x_2$ 在操作前存在、且在操作前没有序列使用过编号 $x_3$。

数据范围：$1 \le n, q, C_m, C_l \le 5 \times {10}^5$。

---

一个不用线段树合并维护摩尔投票的做法。

链表维护序列，线段树维护值域。操作一二四是平凡的，询问众数可以直接在这些线段树上二分中位数。由于题目中众数的定义，这个序列如果存在众数，则一定是这个序列的中位数。

二分出来中位数之后再检查一下是否出现次数超过 $\frac{n}{2}$ 即可。

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

Luogu 3674

给你一个序列 $a$，长度为 $n$，有 $m$ 次操作，每次询问一个区间是否可以选出两个数它们的差为 $x$，或者询问一个区间是否可以选出两个数它们的和为 $x$，或者询问一个区间是否可以选出两个数它们的乘积为 $x$ 。选出的这两个数可以是同一个位置的数。

数据范围：$n\le 10^5$。

---

莫队配合 bitset。

操作一可以维护一个 $10^5-x$ 是否出现过的 bitset，然后稍微推一下移位什么的就可以了。操作二同理。操作三直接枚举 $x$ 的约数，看两个约数是否都出现过。

时间复杂度 $O(n\sqrt m+\frac{mn}{w})$。

Luogu 8353

给定一棵树，要求支持：链加、链求和。

数据范围：$n\le 7\times 10^6, m\le 50000$。

空间限制 64MB。

---

毒瘤空间限制不让我们用树剖，就上树分块。

把路径拆成散块和整块，关键点之间直接按照分块的思路打标记，散点直接暴力加。

随机撒关键点，并且向上标记建出来虚树，同时记录虚树上每个点走哪个儿子第一个到达的关键点，记为 $nxt[u][son]$。

几个关键函数，实现完了就基本做完了：

dep(u)：获得 $u$ 的深度，直接预处理出每个关键点的深度，查询的时候直接暴力跳到关键点。

bottom(u)：得到 $u$ 往下走遇到的第一个关键点。我们先暴力向上跳到关键点，然后用我们预处理的 $nxt$ 查询即可。

lca(u, v)：不用多说了。我们先两个点都暴力向上跳到第一个关键点，如果第一个关键点相等，就直接朴素 lca 即可。否则就求出这两个关键点的 lca，一定就是我们要求的两个点的 lca。

这三个函数搞完基本就做完了，$O(\sqrt n)$ 数组随便开，空间复杂度 $O(2n+\frac{n}{w}+O(\sqrt n))$。

Luogu 3722

给定排列 $a$，定义区间 $[l, r]$ 的价值为：对于 $i, j$（$l\le i<j\le r$），设 $mn=\min_{k=i+1}^{j-1} (a_{k}), mx=\max_{k=i+1}^{j-1}(a_k)$，如果 $mx<\min(a_i,a_j)$，会造成 $p_1$ 的贡献；如果 $\min(a_i, a_j)<mx<\max(a_i, a_j)$，会提供 $p_2$ 的贡献，区间的价值就是造成的贡献和。

$q$ 次询问区间 $[l, r]$ 的价值。

数据范围：$n, m\le 2\times 10^5$。

---

先用单调栈求出对于每个点，其左/右侧第一个大于它的数 $l_i, r_i$。那么它会对这些点对造成贡献：

• $(l_i, r_i)$ 贡献 $p_1$。
• $(x, r_i)$ 贡献 $p_2$，其中 $l_i<x<i$。
• $(l_i, x)$ 贡献 $p_2$，其中 $i<x<r_i$。

然后就是一个二维数点状物了，其中由于又有行加又有列加不好维护，因为询问区间关于 $y=x$ 对称，可以直接进行对称，翻转到列加。

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

Luogu 3733

给定一张图，边有边权 $w$。$q$ 次操作：

• 添加一条边
• 删除一条边，保证删除的边为一操作加入的。
• 修改边权，限制同上。

每次操作后询问从 $1$ 号点开始的最大异或和路径。

数据范围：$n, m\le 500, q\le 1000,w\le 2^{1000}$。

---

简单题，最大异或和路径套路：找出所有的环，插入线性基即可。线性基删除操作难搞就上线段树分治即可。

题目很好，保证了不改原有的边，因此一开始求个 dfs 树就可以。

时间复杂度 $O(\frac{q\log q\log^2w}{\omega})$。

Luogu 5327

在一个遥远的国度，有 $n$ 个城市。城市之间有 $n - 1$ 条双向道路，这些道路保证了任何两个城市之间都能直接或者间接地到达。

国王下令设计了 $m$ 种通用语，并进行了 $m$ 次语言统一工作。在第 $i$ 次统一工作中，一名大臣从城市 $s_i$ 出发，沿着最短的路径走到了 $t_i$，教会了沿途所有城市（包括 $s_i, t_i$）使用第 $i$ 个通用语。

一旦有了共通的语言，那么城市之间就可以开展贸易活动了。两个城市 $u_i, v_i$ 之间可以开展贸易活动当且仅当存在一种通用语 $L$ 满足 $u_i$ 到 $v_i$ 最短路上的所有城市（包括 $u_i, v_i$），都会使用 $L$。

求有多少对城市 $(u, v)$（$u < v$），他们之间可以开展贸易活动。

数据范围：$n\le 10^5$。

---

可以对于每个点求出它能和谁开展贸易活动，那么最终答案就是这些点的答案之和除以 $2$。

显然题目中的要求可以转化为：对于所有覆盖了点 $u$ 的路径 $(x, y)$，将 $x, y$ 加入集合 $S$，求的就是集合 $S$ 构成虚树的大小。这是个经典结论：虚树大小等于按照 dfn 排序后，$\sum_{i=1}^{|S|}dep_{u_i}- \sum_{i=1}^{|S|-1}dep_{\text{lca}(u_i, u_{i+1})}-dep_{\text{lca}(u_1, u_{|S|})}$。于是可以用线段树合并维护 $S$ 中的点以及其 dfn。

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

Luogu 9058

给定一棵有边权的无根树，需要回答一些询问。

定义 $dist(i,j)$ 代表树上点 $i$ 和点 $j$ 之间的距离。

对于每一组询问，会给出 $l,r$，你需要输出 $\min(dist(i,j))$，其中 $l\leq i < j \leq r$。

数据范围：$n\le 2\times 10^5, q\le 10^6$。

---

考虑如果 $dist(i, j)\le dist(x,y)$，其中 $x<i<j<y$，那么 $(x, y)$ 这个点对就没有用处了。因此可以找出所有这样的有用的点对。

进行一个点分治，在分治中心 $rt$ 处求出所有点到它的距离 $c_u$，那么 $dist(u, v)\le c_u+c_v$。可能会出现 $u,v$ 在一颗子树内的情况，但是不需要担心，因为距离只有小的时候才可能会支配别的点对，放大是不会产生新的支配关系的。

考虑三个点 $i, j, k$（$i<j<k$），如果 $(i, j)$ 不被支配，则需要满足 $dist(i, k)<dist(i, j)$ 以及 $dist(i, k)<dist(j, k)$。展开可得 $c_k<c_j$ 且 $c_i<c_j$。由此可得：当 $(i, j)$ 之间所有的 $c$ 都大于 $c_i$ 和 $c_j$ 时 $(i, j)$ 不被支配。

那么直接进行一个单调栈，维护一个单调不减的单调栈，$p$ 加入后弹栈顶，栈顶和 $p$ 即为有效点对。

由此也可以得到每个点在每轮分治中最多产生 $O(1)$ 个有效点对，因此点的数量是 $O(n\log n)$ 的。

后面二维数点即可。时间复杂度 $O((n+q)\log^2 n)$。

Luogu 4565

给定两棵树，求下面这个式子的最大值：

$$\mathrm{depth}(x) + \mathrm{depth}(y) - ({\mathrm{depth}(\mathrm{LCA}(x,y))}+{\mathrm{depth'}(\mathrm{LCA'}(x,y))})$$

数据范围：$n\le 366666$。

---

对第一棵树边分治，选择一条边之后，对于某个这条边上半部分中的点 $u$，它和下半部分所有点的 $\text{lca}$ 都是固定的。因此式子中 $dep_x-dep_{\text{lca}(x, y)}$ 这一部分就可以看作是 $v_x$。剩下的是 $dep_y-dep'_{\text{lca}(x, y)}$，考虑把上下两部分所有点拿出来在第二棵树上建虚树。在 $\text{lca}$ 处合并，因此在虚树上记录子树内 $v$ 的最大值和 $dep$ 的最大值，合并即可。

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

Luogu 7897

给定一颗 $n$ 个节点有根树，第 $i$ 节点权值为 $a_i$。

在这个树上支持一种询问：

• 给定节点 $u$ 和参数 $x$，假如所有节点点权加 $x$，在这种情况下，求：对于所有完全在 $u$ 子树内并包含 $u$ 的连通点集，权值之和最大可能为多少。询问互相独立。

数据范围：$n,m\le 10^6, |a_i|, |x|\le 10^8$。

---

先写出朴素的转移方程：

$$f_u=a_u+\sum_{v\in son_u}\max(f_v, 0)$$

发现恶心人之处为这个取 $\text{max}$，考虑去掉它。让所有满足 $f_u\ge 0$ 的 $u$ 向其父亲连边，那么一个点的 $f$ 值即为其子树和。

把询问离线下来，按 $x$ 扫描线，由于只会加入边不会删除边，因此可以维护。用树状数组链加单点查即可。

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

Luogu 3642

给定一棵树，边有边权，将一条边边权从 $x$ 修改到 $y$ 需要花费代价 $|x-y|$。求让所有叶子节点到根节点距离相等的最小花费。

数据范围：$n\le 600000$。

---

设 $f_{u, x}$ 为 $u$ 子树内叶子节点到 $u$ 距离都为 $x$ 的最小代价。转移为：

$$f_{u, x}=\sum_{v\in son_u}\min_{y\le x}(f_{v, y}+|w-x+y|)$$

朴素转移是 $O(nw^2)$ 的。考虑把 $f_v$ 看作函数 $f_v(x)$，把 $f_v$ 对 $f_u$ 的贡献看作一个函数 $F_v(x)$，归纳可得 $F_v(x)$ 和 $f_v(x)$ 都是凸函数，因此会有斜率为 $0$ 的部分，将斜率为 $0$ 部分左端点记为 $L$，右端点记为 $R$。

上面的式子其实可以看作给定一个 $x$，有一个凸函数，现在有一个绝对值函数，求当 $y$ 等于多少时 $f_{v, y}+|w-x+y|$ 取到最小值。

进行一个分讨：

1. 当 $x<L$ 时，容易发现当 $y=x$ 时的代价是最小的，因为在 $L$ 左侧，$f_v(y)$ 的斜率是小于等于 $-1$ 的，因此向右移动取值点不会使得答案变大，所以取到 $y=x$。
2. 当 $x>R+w$ 时，这时和上面类似，要让取值点尽可能左移，因此当 $y=R$ 时为最优决策点。
3. 当 $L+w\le x\le R+w$ 时，可以观察到绝对值函数的零点就落在 $[L,R]$ 这段区间，因此让 $y=x-w$ 是更优的。
4. 当 $L\le x<L$ 时，情况类似于第一种，让决策点尽量靠右同时不越过 $L$，因此 $y=L$ 最优。

总结一下上面的分讨可以得到下面的转移：

$$F_v(x) = \begin{cases}f_v(x) + w & x \leq L \\f_v(L) + w-x+L & L < x \leq L + w \\f_v(x-w)=f_v(L) & L + w < x \leq R + w \\f_v(R) + ((x - R) - w) & R + w < x\end{cases}$$

同时还能发现 $F_v(x)$ 其实是个连续函数，因此只需要使用可并堆维护拐点即可。

后面维护的内容比较平凡，略过。

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

CF1034D

有 $n$ 个区间 $[a_i,b_i]$。定义区间的区间 $[l,r]$ 的价值是第 $l$ 个区间到第 $r$ 个区间的并的长度，找出 $k$ 个不同的区间的区间，使得总价值最大。

数据范围：$n\le 3\times 10^5, k\le 10^9$。

---

考虑一个弱化版：$q$ 次询问，每次询问编号 $[l, r]$ 中的区间的并的长度。考虑离线扫描线，右端点向右移动一位，将数轴上 $[l_i, r_i]$ 这些位置全部染成颜色 $i$，那么某个位置之前的颜色会被覆盖。记 $f_i$ 为当前固定右端点 $r$ 后，编号 $[l, r]$ 中区间的并的长度。如果这次区间赋值把一段长度为 $len$，颜色为 $v$ 的颜色段覆盖了，就说明在右端点为 $[v + 1, i]$ 的时候这段区间没被覆盖，让 $f_{v+1\sim i}$ 全部加上 $len$ 即可。

求出前 $k$ 大可以二分求出第 $k$ 大，把所有大于等于这个数的数统计上即可，线段树区间加以及线段树上二分即可。这时带的是俩 $\log$，过不去，考虑优化。区间加可以差分维护，大于等于 $mid$ 的 $f$ 的最靠右的端点单调不降，可以双指针维护。

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