PKUWC2024 Day2 简要题解

· · 题解

T2

题意

给定希尔排序的数组 d，求在所有长度为 n 的排列中，能最大化希尔排序操作数的排列数量和相应操作数。

题解

希尔排序的一次操作是交换一个逆序对，我们考虑把这次操作的贡献记录在较大的值上，一个排列的操作数即为其每个值的贡献之和。此时，对于任意排列，其最大值的贡献都只和最大值的初始位置有关，并且这一贡献可以通过希尔排序计算。

考虑任意一个最大值之外的数，会发现它的贡献只与它的位置和比它大的数的位置集合有关。因此可以把比它大的数的位置集合状压并进行 dp，枚举当前值的位置进行转移，转移时的贡献计算可以通过一次希尔排序得到，复杂度 O(2^n\operatorname{poly}(n))。

注意到对于希尔排序第一轮中的一个组，比当前考虑的值它大的数必然都在这个组的最左侧，否则显然不优。因此对于一个大小为 x 的组，它可能的状态数只有 d+1 种，则可以将状态精简为 O\left(\left(\dfrac{n}{d_1}\right)^{d_1}\right)。如果仍然通过希尔排序计算转移时的贡献，则可以获得 76 分。

瓶颈在于希尔排序计算贡献，我们抽象一下这部分的问题：

考虑用记忆化搜索求解该问题。称希尔排序的每个 d_i 对应的全部 d_i 次插入排序为一轮操作。则在第 i 轮操作后，每一组必然是有序的，其 1 的分布只有 O\left(\left(\frac{n}{d_i}\right)^{d_i}\right) 种，加上 0 的位置，状态数为 O\left(\left(\frac{n}{d_i}\right)^{d_i}\cdot n\right)。因此如果使用记忆化搜索存下每一轮时的答案，则总状态数为 O\left(n\sum\limits_{i=1}^n\left(\frac{n}{d_i}\right)^{d_i}\right)，可以通过。

T3

题意

有 n 个栈，初始全为空，需要支持一下三种操作：

  1. 在第 l\sim r 个栈中都加入 x 个 y
  2. 在第 l\sim r 个栈中都弹出 w 个元素，如果栈为空则停止。
  3. 查询第 k 个栈中从栈底开始的第 p\sim q 个元素之和，如果不存在则为 0。

题解

考虑离线，从左到右扫描每个下标，维护一个时间轴，如果一个修改作用于该下标则在时间轴的相应位置存在此修改。则原先的修改相当于在 l 处加入，在 r+1 处删除。

对于一个 t 时刻的询问，相当于我们要求出时间轴上从 1 到 t-1 时刻所有修改构成的栈，且支持快速查询其元素的前缀和。我们可以刻画依次进行若干个修改后的总体效果，即为先进行若干次 pop，再进行若干次 push。

考虑对时间轴分块，每个块维护块中所有修改的总体效果。修改时暴力重构，查询时从后往前暴力遍历所有块，对于后方的 pop 直接二分其在 push 序列中对应的位置。总复杂度 O(n\sqrt{n}\log n)，由于一个块内的 push 序列通常较小，因此常数不大，据说最慢点 <400\texttt{ms}。

也可以使用单侧递归线段树维护时间轴，每个线段树节点存放其对应时间区间中所有修改的总效果，具体只维护 pop 数，push 数，push 的所有数的总和。维护方式与著名的查询区间前缀最大值个数的单侧递归线段树类似。

查询时，仍然是从后往前处理。传入右侧（时间后方）有几个 pop，如果超过右子树 push 数则不需要递归进入右子树，否则会对左子树产生影响的 pop 数即为右子树中的 pop 数，是个定值，此时左子树的答案可以通过当前节点的答案与右子树答案作差得到，无需递归。复杂度 O(n\log^2 n)，最慢点 <500\texttt{ms}，甚至跑不过带 log 的分块。

彩蛋：

T3 另解

不对时间和下标进行转置，直接按时间倒序处理修改，用一颗线段树维护所有查询的答案（询问按位置排序）。原先的区间修改仍是区间修改，对于询问，在到达其截止时间时将该询问处的内容清零即可。可以使用 segment tree beats 维护，复杂度 O(n\log^2 n)。