一种求第 k 小方案的神奇做法

同样适用于前 k 大

肯定对于每一个方案 $x$ 都会有一个 $val(x)$ 表示这种方案的权值。

我们定义对于一个集合的 $val$ 是 $val(S)=\min\limits_{x\in S}\{val(S)\}$，首先需要找到一个集合 $S$ 使得 $val(S)$ 是最小的权值，对 $S$ 定义一个 $trans(S)$ 表示 $S$ 能变换到的集合的集合，一般这个 $trans$ 是一个固定的变换方法，这里需要满足 $T \in trans(S) ,val(T) \ge val(S)$ 并且对于任意一个不是权值最小的方案 $T$ 都存在且一个 $S$ 使得 $T \in trans(S)$，这样能保证我们拓展到的集合权值是逐渐递增的。

考虑我们如何维护这个东西，我们用一个堆维护当前的已经被拓展到的方案，取出 $val$ 最小的方案 $S$，然后将 $trans(S)$ 中没有加进过堆的集合全部加入堆中，将 $S$ 弹出堆，重复操作，不难发现我们第 $i$ 弹出堆的元素一定是第 $i$ 小，因为根据上面 $trans$ 的定义是一定能变换到所有方案的，并且从最小方案到当前方案的路径上 $val$ 是递增的，我们这样拓展 $k$ 次一定能找到第 $k$ 小的元素，我们设 $sz$ 表示 $trans$ 集合的大小，$ds$ 表示从集合中找到最大值的复杂度，判断集合是否加进过堆的复杂度是 $O(chk)$，这样时间复杂度是 $O(k\cdot sz\cdot ds\cdot (chk+\log(k\cdot sz)))$，非常优秀。

题目：

P2048 [NOI2010] 超级钢琴

题意：给你一个长度为 $n$ 序列 $A$，求前 $k$ 大的长度属于 $[l,r]$ 的区间 $a_i$ 和。

$n,k \le 5 \times 10^5,-1000 \le a_i \le 1000$。

发现区间不好做，先做前缀和转换成 $\max(a_r-a_l)$，发现对于每一个左端点 $x$ 都有一个 $[l,r]$ 表示右端点能在的位置，我们用堆维护五元组 $S=\left\{x,l,r,val,pos\right\}$ 表示左端点是 $x$ ，右端点选的区间是 $[l,r]$ ，当右端点选 $pos$ 时是最优的，权值为 $val$ ，不难发现 $trans(S)=\left\{\left\{x,l,pos-1,val_{l,pos-1},pos_{l,pos-1}\right\},\left\{x,pos+1,r,val_{pos+1,r},pos_{pos+1,r}\right\}\right\}$，发现 $pos$ 肯定是 $[l,r]$ 中 $a_i$ 最大的 $i$ ，这个可以直接用 $st$ 表维护，$val$ 也就很好算了，这里 $sz=2,ds=O(\log n)$，不会有重复集合加入堆，所以时间复杂度 $O(k \log k\log n)$。

异或粽子和上面那道题基本一样，就不详细说了。

P6230 [BalticOI 2019 Day2]奥运会

题意：有 $n$ 个人，$k$ 个比赛，第 $i$ 个人在第 $j$ 场比赛中的得分是 $a_{i,j}$ 现在一支队伍要选 $k$ 个人，这支队伍每一场比赛的得分为得分最高的那个人的得分，这支队伍的得分为所有比赛的得分的和，现在问你得分第 $C$ 大的队伍的得分

$n\le500,k \le6,C\le2000$

蒟蒻瞎想的做法：link

洛谷题解做法：

首先这个数据范围非常小，所以我们设的一些东西可以非常暴力。

P6646 [CCO2020] Shopping Plans

非常牛逼的一道题！

分成几部分来考虑这道题

Part1

$a_i=1,x=y$

这个还是比较简单的，首先最小值肯定是选前 $x$ 个，然后考虑怎么设计 $trans$，