PKUWC2024 Day2 简要题解
T2
题意
给定希尔排序的数组
题解
希尔排序的一次操作是交换一个逆序对,我们考虑把这次操作的贡献记录在较大的值上,一个排列的操作数即为其每个值的贡献之和。此时,对于任意排列,其最大值的贡献都只和最大值的初始位置有关,并且这一贡献可以通过希尔排序计算。
考虑任意一个最大值之外的数,会发现它的贡献只与它的位置和比它大的数的位置集合有关。因此可以把比它大的数的位置集合状压并进行 dp,枚举当前值的位置进行转移,转移时的贡献计算可以通过一次希尔排序得到,复杂度
注意到对于希尔排序第一轮中的一个组,比当前考虑的值它大的数必然都在这个组的最左侧,否则显然不优。因此对于一个大小为
瓶颈在于希尔排序计算贡献,我们抽象一下这部分的问题:
- 有一个长度为
n 序列,每个元素是0,1 或者-1 。求对它进行希尔排序后,会发生多少次0 和-1 的交换。
考虑用记忆化搜索求解该问题。称希尔排序的每个
T3
题意
有
- 在第
l\sim r 个栈中都加入x 个y - 在第
l\sim r 个栈中都弹出w 个元素,如果栈为空则停止。 - 查询第
k 个栈中从栈底开始的第p\sim q 个元素之和,如果不存在则为0 。
题解
考虑离线,从左到右扫描每个下标,维护一个时间轴,如果一个修改作用于该下标则在时间轴的相应位置存在此修改。则原先的修改相当于在
对于一个
考虑对时间轴分块,每个块维护块中所有修改的总体效果。修改时暴力重构,查询时从后往前暴力遍历所有块,对于后方的 pop 直接二分其在 push 序列中对应的位置。总复杂度
也可以使用单侧递归线段树维护时间轴,每个线段树节点存放其对应时间区间中所有修改的总效果,具体只维护 pop 数,push 数,push 的所有数的总和。维护方式与著名的查询区间前缀最大值个数的单侧递归线段树类似。
查询时,仍然是从后往前处理。传入右侧(时间后方)有几个 pop,如果超过右子树 push 数则不需要递归进入右子树,否则会对左子树产生影响的 pop 数即为右子树中的 pop 数,是个定值,此时左子树的答案可以通过当前节点的答案与右子树答案作差得到,无需递归。复杂度 甚至跑不过带 log 的分块。
彩蛋:
T3 另解
不对时间和下标进行转置,直接按时间倒序处理修改,用一颗线段树维护所有查询的答案(询问按位置排序)。原先的区间修改仍是区间修改,对于询问,在到达其截止时间时将该询问处的内容清零即可。可以使用 segment tree beats 维护,复杂度