P2824 [HEOI2016/TJOI2016] 排序
一、题意
自行理解。
二、思路
1、观察
* 题目没有要求输出整个序列，而是询问单点，猜想可能不用知道整个序列即可。
* 可以转换二分。二分需要一个判定，设最终 qqq 位置的真实值为 vvv，令 check(x)\text{check}(x)check(x) 表示 qqq 位置上的值是否 ≥x\ge x≥x。当 x≤vx\le vx≤v 时，v≥xv\ge xv≥x，check(x)\text{check}(x)check(x) 为真；当 x>vx>vx>v 时，v<xv<xv<x，check(x)\text{check}(x)check(x) 为假。所以可行 xxx 的集合是前缀
[1,v][1,v][1,v]，具有单调性，考虑如何判定\color{#6BCB77}{\text{考虑如何判定}}考虑如何判定。
* 可以令 check(x)\text{check}(x)check(x) 表示 qqq 位置上的值是否 ≥x\ge x≥x，接下来要解决的是这个判定怎么快速算\color{#4DD0E1}{\text{这个判定怎么快速算}}这个判定怎么快速算。
* 既然判定只依赖元素和 xxx 的大小关系，而排序又难以直接维护，不如把序列按阈值 xxx 二值化，也就是 01 转化\color{#6BCB77}{\text{01 转化}}01 转化：ai≥xa_i\ge xai ≥x 记 111，否则记 000。这样排序就变得简单了。
2、细节
整个 010101 数组是这样求出的：令 ai<xa_i< xai <x 为 000，否则为 111；这样后续判断 qqq 位置是否为 111 即可。
010101 序列排序只需数区间内 1 的个数 cnt\color{#4DD0E1}{\text{数区间内 } 1 \text{ 的个数 } cnt}数区间内 1 的个数 cnt：升序把 [l,r−cnt][l,r-cnt][l,r−cnt] 赋 000、[r−cnt+1,r][r-cnt+1,r][r−cnt+1,r] 赋 111；降序把 [l,l+cnt−1][l,l+cnt-1][l,l+cnt−1] 赋 111、[l+cnt,r][l+cnt,r][l+cnt,r] 赋
000。一次排序变成一次区间查询加两次区间赋值\color{#6BCB77}{\text{一次排序变成一次区间查询加两次区间赋值}}一次排序变成一次区间查询加两次区间赋值，线段树维护区间和与区间覆盖即可。
二分时 check(x)\text{check}(x)check(x) 为真则 l=mid+1l=\text{mid}+1l=mid+1，找最大可行 x\color{#FF6B6B}{\text{找最大可行 } x}找最大可行 x，它就是 vvv。
3、时间复杂度
每次 check(x)\text{check}(x)check(x) 为 O(n+mlogn)O(n+m\log n)O(n+mlogn)，二分 O(logn)O(\log n)O(logn) 次，总复杂度为 O((n+m)log2n)\mathcal{O}((n+m)\log^2 n)O((n+m)log2n)，可以通过。
4、易错点
* 二分方向\color{#FF9F43}{\text{二分方向}}二分方向：check\text{check}check 为真时 l=mid+1l=\text{mid}+1l=mid+1，找最大可行 xxx。
* 懒标记\color{#FF9F43}{\text{懒标记}}懒标记要区分“无标记”和“赋 000”，建议用 −1-1−1 表示无标记。
* 推平前判区间非空\color{#FF9F43}{\text{推平前判区间非空}}推平前判区间非空，避免 l>rl>rl>r 时越界。
三、代码
四、总结&TRICK
1、查询改成判定
这个应该是本题的难点，主要是发现了“单点”与“单调性”。
2、010101 化
我认为可以先需要离散化，后续发现直接 010101 即可。
