总力站 #2 冒泡排序
lgswdn_SA
·
2024-06-25 18:32:38
·
个人记录
四刀过了（指写的第四份代码）...真菜啊。
希望以后不要想这么多假贪心。
首先考虑 l=r 如何做。这个是简单的，相当于限制了一些位置的取值（设限定了这个位置是 a_i），又由于没有限制的一定是递增的，所以取 x 的代价相当于左侧 a > x 的个数加上右侧 a 然后考虑区间不交怎么做。这个是复杂的，因为每个位置有下界 l_i>但是我们可以仔细分析。我们对于 x 关于这一步我的唐诗多刀过程：一开始我错误地认为每个位置的代价关于取值是单峰的。于是我考虑每次 x\to x+1，然后考虑每个位置是否变成 x+1 会更优。于是考虑 x\to x+1 会有哪些变化：实际上就是上面说的，右侧 a\le x 的，减去左侧 l 或 a\le x+1 的，就是变化量。 虽然不是单峰的，但是我们把这个差分给前缀和了，就得到了上面的结论了。 区间有交转化成无交是 trivial 的。 https://uoj.ac/submission/693427