原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个位置上的具体值
1.2 题目背景、允许、禁止与限制
背景：
有一个有 nnn 个元素的排列（说明其中每种元素只有一个）
允许：
要进行 mmm 次操作，每次操作有两种可能
* 将区间 [l,r][l,r][l,r] 的数字按升序排序
* 将区间 [l,r][l,r][l,r] 的数字按降序排序
最后求操作完成之后序列的第 qqq 项
限制：
1.3 题目数据范围与猜测
1≤n,m≤105⟶O(n log n)1 \le n, m \le 10^5 \longrightarrow O(n~log~n)1≤n,m≤105⟶O(n log n)
1.4 一句话概括题意
有一个排列，求经过一些排序操作后某一特定位置元素值
2 题目破题推导
这题只会在若干操作完毕后求一次值！
3 模型匹配
那既然 “这题只会在若干操作完毕后求一次值”，那么
我们可以考虑 线段树离线做法\huge{线段树离线做法}线段树离线做法
简要概括步骤：
1. 二分答案\huge{二分答案}二分答案 猜排序操作完成后 aq=mida_q=midaq =mid
2. 那check函数里面呢？
2.1. 把 ≥mid\ge mid≥mid 的数都赋值为 111
2.2. 把 <mid<mid<mid 的数都赋值为 000
2.3. 回归线段树\huge{线段树}线段树，维护区间和
2.4. 将 [l,r][l,r][l,r] 升序排序
①查询区间和 num=[l,r]→num=[l,r]\rightarrownum=[l,r]→ 这一步等价于找其中有多少 ≥mid\ge mid≥mid 的数
②将 [r−num+1,r][r-num+1,r][r−num+1,r] 修改为 1→1\rightarrow1→ 这一步等价于把所有 ≥mid\ge mid≥mid 的数放在 midmidmid 后面（这不就是升序排序吗？）
③将 [l,r−num][l,r-num][l,r−num] 修改为 0→0\rightarrow0→这一步等价于把所有 <mid< mid<mid 的数放在 midmidmid 前面（这不就是升序排序吗？）
2.5. 将 [l,r][l,r][l,r] 降序排序
①查询区间和 num=[l,r]→num=[l,r]\rightarrownum=[l,r]→ 这一步等价于找其中有多少 ≥mid\ge mid≥mid 的数
②将 [l,l+num−1][l,l+num-1][l,l+num−1] 修改为 1→1\rightarrow1→ 这一步等价于把所有 <mid< mid<mid 的数放在 midmidmid 后面（这不就是降序排序吗？）
③将 [l+num,r][l+num,r][l+num,r] 修改为 0→0\rightarrow0→这一步等价于把所有 ≥mid\ge mid≥mid 的数放在 midmidmid 前面（这不就是降序排序吗？）
2.6. 查询结果
所有升序降序操作结束之后查询区间 k=[q,q]k=[q,q]k=[q,q]
如果 k=1k=1k=1，则说明 midmidmid 猜小了（当然有可能是对的，因为前面是 ≥\ge≥）
如果 k=0k=0k=0，则说明 midmidmid 猜大了
4 最终代码（禁止抄袭，仅用于参考）
