不是 DE_aemmprty 的草稿纸

关于难度

• \(\textbf{Easy}\)：我是 zak，我一眼秒了，我觉得这题没啥技巧啊！
• \(\textbf{Medium}\)：完全自己想出，但想了较长时间。
• \(\textbf{Hard}\)：不完全是自己想出。

\([0, 1]\) 表示在同档题中的难度。

qoj12212 \(\textbf{[*Medium 0.1]}\)

二分答案。考虑确定 \(\max = t\) 之后如何判定。因为容易发现将序列循环位移不影响答案，所以不妨设 \(a_1 = \min\limits _{i = 1} ^ n a_i\)。为了处理方便，可以令 \(a_{n + 1} = a_1\)，并将 \(k\) 增加 \(1\)，显然任意选取 \(\ge 2\) 个数的方式都可以选上 \(a_1\) 与 \(a_{n + 1}\)，故不妨这两个数始终被选中。首先套路地将 \(\le \dfrac{x}{2}\) 的称为"小数"，\(> \dfrac{x}{2}\) 的称为"大数"，则显然选出的数中小数相邻无限制，大数不能相邻。

先证明存在一种选取最多数的方法使得所有小数都被选取。这是因为若小数 \(x\) 未选中，设 \(x\) 两侧最近的被选中的小数为 \(l, r\)，去掉 \(l, r\) 之间选取的至多一个大数，再选上 \(x\)，选中的数的个数不减。

故不妨所有小数都选，此时对两个相邻的小数 \(a_l, a_r\)，它们中间至多选出一个大数。我们只需判断 \(\min\limits_{i = l + 1} ^ {r - 1}a_i\) 与 \(t - \min\{a_l, a_r\}\) 的大小关系即可。用 ST 表即可做到 \(\mathcal{O}(n (\log n + \log V))\)。

arc183_d \([\textbf{*Hard 0.3}]\)

先考虑有完美匹配的充要条件。首先显然点数为偶数，且这个条件在操作过程中始终满足。我们任意确定一个点为根，考虑如何确定一个点所匹配的点。我们记 \(s_x = siz_x \bmod 2\)，其中 \(siz_x\) 表示 \(x\) 的子树大小，那么容易发现 \(s_x = 1\) 与 \(x\) 和其父亲匹配等价。又因为和父亲匹配的点数和与儿子匹配的点数相等，可知 \(s_x = 0/1\) 的点数相等。

另一方面，若 \(s_x = 0/1\) 的点数相等，由于每个 \(s_x = 0\) 的点至少有一个子节点满足 \(s_x = 1\)，可知 \(s_x = 1\) 的点数不少于 \(s_x = 0\) 的点数。故所有 \(s_x = 0\) 的点都恰有一个 \(s_x = 1\) 的子节点，且 \(s_x = 1\) 的点所有子节点都有 \(s_x = 0\)，此时显然存在完美匹配。

再考虑顶点间距离和的最大值，这个问题的套路是以重心为根，最大值即所有结点的深度之和，在每次取重心的不同子树中的点时取等，即每条两个顶点间的路径都过根，我们猜测这是可以做到的。

考虑怎么样的修改保持存在完美匹配的性质，这其实相当于一个逆向的找增广路的过程，即要求匹配边和非匹配边交替出现，且开头结尾都是匹配边。根据是否为匹配边的条件可以知道，该条件相当于路径上的点 \(s_x\) 满足 \(0,1\) 交替（特别规定根不在路径上），修改后，所有路径上的 \(s_x\) 都会 \(\text{xor }1\)。我们发现除了有一个点来自于根的满足 \(s_x = 1\) 的子节点的子树（这样的子树只有一个）的要求外，该要求关于路径的两个端点独立，这启发我们转为考虑每次删一个点，满足到根路径上 \(0, 1\) 交替的条件。确定删点顺序是关于每个子树独立的（在只考虑到该子树的根的路径的情况下），所以可以自底向上进行归纳构造。

在考虑到 \(x\) 时，我们假设其所有子树删点顺序已确定。

• \(s_x = 1\)，我们可以以任意顺序依次删空每一个子树。
• \(s_x = 0\)，先删空满足 \(s_y = 1\) 的子结点 \(y\) 的子树，再删空其他子树即可。

最后记得删掉 \(x\)。

在考虑到根时，其所有子节点删点顺序已经确定。我们每次将 \(s_x = 1\) 的子结点 \(x\) 和剩余子结点中 \(siz\) 最大的子结点 \(y\) 配对（即把 \(x, y\) 子树中按顺序的下一个点配对删除），此时 \(s_x = 1\) 的子结点变为 \(y\)，且 \(siz\) 容易维护。由于 \(s_x = 1\) 的子树始终只有一个且 \(siz\) 最大的子树始终不超过总点数的一半，所以可以删空。用优先队列维护即可，复杂度 \(\mathcal{O}(n \log n)\)。

arc182_c \([\textbf{*Medium 0.2}]\)

注意 \(1, 2, \cdots, m\) 的素因子共 \(8\) 个，考虑和 \(2 ^ {\pi(m)}\) 有关的复杂度。对序列 \(a_1, a_2, \cdots, a_n\)，我们设 \(\alpha_{i, j} = v_{p_j}(a_i)\)，即 \(a_i\) 中 \(p_j\) 的幂次，则该序列权值为 \(\prod\limits_{j = 1} ^ 8 (1 + \sum\limits_{i = 1} ^ n \alpha_{i, j})\)。考虑展开乘积，并考虑每一项的贡献位置。我们将 \(dp_{i, S}\) 设为对 \(x \in S\)，\(\alpha_{j, x}\) 所选取的项满足 \(j \le i\) 造成的贡献之和，即只考虑 \(S\) 中素因子时长度为 \(i\) 序列的答案。转移时我们枚举 \(S\) 并枚举 \(a_i\) 中造成贡献的素因子（\(0\) 或 \(1\) 个）即可，用矩阵快速幂优化可以做到 \(\mathcal{O}(2 ^ {3 \pi(m)} \log n)\)。

这么说比较抽象，我认为更好的理解方式是看成集合幂级数 \(f\) 的 \(n\) 次方，其中 \(f_{\emptyset} = 1\)，\(f_{\{i\}} = \sum\limits_{j = 1} ^ m v_{p_j}(i)\)，这个意思也是考虑 \(\{a_n\}\) 每一项在乘积中贡献了那些括号中的数，然后倍增并暴力计算集合幂级数乘法就可以做到 \(\mathcal{O}(3 ^ {\pi(m)} \log n)\)，注意题目问的是长度 \(\le n\)，这也是容易维护的。

qoj11405 \([\textbf{*Medium 0.3}]\)

首先在起点处断环为链，注意到 \((x, y)\) 无法收集当且仅当 \(x\) 的位置均在 \(y\) 之后，所以在不考虑交换的情况下容易用扫描线 + BIT 处理出以每个 \(i\) 为起点的收集类型数量 \(s_i\)。

再考虑交换的影响，我们猜想每一次交换都恰能使数量增加 \(1\)。一方面，显然增加量不超过 \(1\)。另一方面，我们只需要找到两种颜色 \(x, y\) 使 \(x\) 的位置均在 \(y\) 之后且有一对 \(x, y\) 颜色相邻。我们先找到 \(x_1 < x_2 < y_1 < y_2\) 使 \(x_1, x_2\) 和 \(y_1, y_2\) 颜色相同，分别为 \(x, y\)。考虑 \(x_2 + 1\)，若与 \(x_2 + 1\) 颜色 \(c\) 相同的位置在其之后，则颜色 \(x, c\) 成立，否则颜色 \(y, c\) 的位置的最近距离比 \(x, c\) 更近，至多进行有限次这样的过程。

故每个点为起点对答案的贡献形如一条在 \([0, s_i)\) 初始斜率为 \(0\)，在 \((s_i, n ^ 2]\) 斜率为 \(X\) 的折线，按 \(s_i\) 排序，则只需考虑 \(c_i - Xs_i\) 为前缀最小值的 \(i\)，且若 \(s_i \le s_j, c_i \ge c_j\)，不考虑 \(i\)。对于每个询问二分出 \(s_u \le K_q \le s_v\)，则取起点为 \(u, v\) 的答案的 \(\min\) 即可，总复杂度为 \(\mathcal{O}((n + q) \log n)\)。

qoj11411 \([\textbf{*Easy 0.9}]\)

用 dfn 序刻画在子树内，我们只需要考虑有哪些深度上的权值被合并到深度为 \(i\) 的位置，用线段树合并维护即可。对于修改，直接在对应深度的线段树上修改即可，复杂度 \(\mathcal{O}((n + q) \log n)\)。

qoj8640 \([\textbf{*Medium 0.1}]\)

先考虑判断可行性，我们设 \(x_i\) 为仅使用操作 \(2\) 使第 \(1, 2, \cdots, i\) 条鱼智力均与 \(c_j \bmod D\) 相同时第 \(i\) 条鱼的智力最小值除以 \(D\) 下取整的值，容易发现 \(x_i = x_{i - 1} + [c_i \bmod D < c_{i + 1} \bmod D]\)。记 \(y_i = \lfloor\dfrac{c_i}{D}\rfloor - x_i\)。则对于区间 \([l, r]\)，根据 \(x\) 的递推可以发现此时类似定义的 \(x_i\) 会变为 \(x_i - x_l\)，故可行当且仅当 \(\min\limits_{i = l} ^ r y_i + x_l \ge 0\)。

可以发现对于 \(l \le i \le r\)，为了保证进行操作 \(1\) 后所有的鱼的智力不超过 \(c\)，对 \(i\) 进行操作 \(2\) 至少 \(y_i - \min\limits_{j = i} ^ r y_j\) 次，使用楼房重建线段树即可。也可以离线维护单调栈并二分，复杂度 \(\mathcal{O}(n + q \log n)\)。

qoj8641 \(\textbf{[*Medium 0.6]}\)

首先考虑 \(h_i\) 确定时怎么做，先给 \(h\) 排序，设 \(h\) 中有 \(c_1\) 个 \(1\)，\(c_2\) 个 \(2\)，\(\cdots\)，\(c_m\) 个 \(m\)，则对任意 \(k\)，前 \(\sum\limits_{i = 1} ^ k c_i - 1\) 个 \(\le k\) 的数（除去最小值）会向 \(\le k - 1\) 的共 \(\sum\limits_{i = 1} ^ {k - 1} c_i = \sum\limits_{i = 1} ^ k c_i - c_k\) 个数连边。所以当 \(c_k \neq \max\limits_{i = 1} ^ k c_i\) 时，可以让所有 \(k\) 都连向每个点原有的连接设施，且若不是这样可以通过交换进行调整。而 \(c_k = \max\limits_{i = 1} ^ k c_i\) 时，会多出 \(c_k - \max\limits_{i = 1} ^ {k - 1}\) 条边无法连接原有的设施，此时会造成 \(\left(\min\limits_{i = 1} ^ {\sum_{i = 1} ^ {k - 1} c_i} C_i\right)\left(c_k - \max\limits_{i = 1} ^ {k - 1} c_i\right)\) 的贡献。

考虑 dp，记 \(f_{i, j, k}\) 为考虑 \(\le i\) 的数时，对 \(1, 2, \cdots, i - 1\) 操作后 \(i\) 有 \(j\) 个且 \(1, 2, \cdots, i - 1\) 中最多的数有 \(k\) 个的最小成本。考虑转移。设初始时有 \(c\) 个 \(h_s = i + 1\)，有 \(t\) 个 \(i\) 会操作至 \(i + 1\)。对于建造连接设施的贡献，显然我们可以保证对 \(h\) 排序后 \(c\) 的前缀最小值高度不变（因为对于每一个存在 \(h_i = x\) 的 \(x\)，对 \(h\) 操作时不会同时操作所有 \(\ge x\) 的数，一定会剩下至少一个 \(h_i = x\)，可以让 \(c\) 的前缀最小值不被操作），知对应的 \(\min\limits_{i = 1} ^ {\sum_{i = 1} ^ {k - 1} c_i} C_i\) 为所有初始时 \(h \le i - 1\) 的数中 \(c\) 的最小值，记其为 \(C\)，那么转移为 \(f_{i + 1, t + c, \max(j - t, k)}\) 对 \(f_{i, j, k} + Kt + \max(0, j - t - k)C\) 取 \(\min\)，可以做到 \(\mathcal{O}(HN ^ 3)\)。注意初值为 \(f_{0, 0, 1} = 0\)。

考虑优化 dp 转移，按上述方式转移较难优化，设初始时有 \(c\) 个 \(i + 1\)，考虑 \(f_{i + 1, j + c, k}\) 由什么转移过来。首先发现 \(Kj\) 这一项始终存在，可以最后加上。讨论 \(k\) 来自 \(i\) 的个数还是 \(1, 2, \cdots, i - 1\) 的个数。记 \(C\) 为所有初始时 \(h \le i - 1\) 的数中 \(c\) 的最小值。

• \(k\) 为 \(1, 2, \cdots, i - 1\) 的个数的最大值，从 \(\min\limits_{x = 0} ^ {\min(n, j + k)}f_{i, x, j}\) 转移，可以使用前缀 \(\min\) 优化。
• \(k\) 为 \(i\) 的个数，从 \(\min\limits_{x = 1} ^ j f_{i, j + k, x} + (k - x)C = \min\limits_{x = 1} ^ j f_{i, j + k, x} + (j + k - x)C - jC\) 转移过来，处理 \(f_{i, j, k} + (j - k)C\) 的前缀 \(\min\) 即可。

故复杂度可优化为 \(\mathcal{O}(HN ^ 2)\)。

再考虑在复杂度中去掉 \(H\)，显然考虑离散化，将 \(h\) 划分为若干段，设 \(h\) 有对于 \(a_1\) 个 \(b_1\)，\(a_2\) 个 \(b_2\)，\(\cdots\)，\(a_m\) 个 \(b_m\)，满足 \(a_1 < a_2 < \cdots < a_m\)，找到最小的 \(k\) 满足 \(b_1 + \sum\limits_{i = 1} ^ {k} a_i - 1 < b_k\)（若没有则令 \(k = m + 1\)），则前 \(\sum\limits_{i = 1} ^ {k - 1} a_i\) 个数可以通过 \(+1\) 调整至 \(b_1, b_1 + 1, \cdots, b_1 + \sum\limits_{i = 1} ^ {k - 1} a_i - 1\) 使其互不相同，故不会把 \(b_1, b_2, \cdots, b_{k - 1}\) 增加至 \(b_1 + \sum\limits_{i = 1} ^ {k - 1} a_i\) 及以上，故在 \(< b_k\) 的值域可以只保留这 \(\sum\limits_{i = 1} ^ {k - 1} a_i\) 个数。对于 \(\ge b_k\) 的数继续类似分段，可以将值域限制在 \(\sum\limits_{i = 1} ^ m a_i = N\) 个数中，故总复杂度为 \(\mathcal{O}(N ^ 3)\)。