首先 $c$ 没什么卵用,我们直接把他乘到属性里。

可以发现这里的 $d$ 是两个属性值减一减的绝对值,所以我们要考虑怎么维护这个绝对值。

我们先考虑 $K = 1$ 的情况,先把这些生物按照 $d$ 的大小排个序,那么后一个减前一个的值一定就是非负的,也就等于绝对值,直接扫一遍就好了。

接下来考虑 $K \not = 1$ 的时候的前 $K - 1$ 位,根据幼儿园学过的知识我们可以知道:

$$a - b \leq |a -b|$$

由于我们要求绝对值的和的最大值,所以我们只要枚举每个属性的正负把他们一起取最大值即可。

那么第 $K $ 位怎么办呢?我们可是要加上绝对值的相反数啊。没关系,采用之前 $K = 1$ 的时候的方法,减一减扫过去,就能保证你去到的值非负啦。

这题需要用到一个惯用的套路。

$$a - b \leq |a - b|$$

显然如果是 $a - b$ 非负的,直接取等号;如果 $ a - b $ 负数,那么绝对值就是正数,负数一定小于正数。

考虑到 $ 2 ^ 5 ​$ 并不是很大,我们可以暴力枚举每个数的符号(用状态压缩的方式)。然后维护一棵线段树进行修改和查询即可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×