JOI2016]

洛谷https://www.luogu.com.cn/problem/P2824

问题思路

本文介绍一种二分答案的做法时间复杂度为(nm)*log(n)*log(n).本题存在nlog(n)的做法然而其做法没有二分答案的做法通俗易懂.

二分枚举答案为mid对于原序列中大于或等于mid的元素将其转化为1对于其他元素将其转化为0.现在原排列已转化为01序列m次操作对01序列进行排序.经过m次排序操作后如果第p个位置上的元素为1那么更新二分边界

mid.如何维护m次操作呢该问题转化为线段树的修改查找问题。

没有接触过线段树修查问题的读者建议先去学习相关知识此处不多赘述.

好了思路介绍完了你可能惊讶于为什么二分答案可行.如下便是二分答案可行性的一些解释.

假如经过m次操作后第p个位置上的元素为x0。

我们考虑m次普通的序列排序但是此次排序咱们让每一个元素都夹带“私货”.对应于问题思路中的第一步令mid

x0对于xmid的元素让它带上额外的元素1.对于xx0的元素让它带上额外的元素0.经过m次操作后元素x0位于第p个位置上且额外的“私货”——元素1也随之到达了第p个位置.

mid

依旧会随着元素x0来到第p个位置上.然而假如midx0那么跟随元素x0到达第p个位置上的额外“私货”便是元素0了.

当我们不再考虑普通的序列排序而是考虑01序列的排序时对元素0和1进行排序后的结果必定能够映射到其普通序列的正确的排序结果上.举个例子对序列

perm

[0,0,1,1,1]该排序结果能够映射到其普通序列的正确排序结果上即

perm