原题链接
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 题目破题推导
这题只会在若干次操作后求一次值
2.1 第一步：正向思维转逆向思维
正向思维：多次区间排序互相影响，非常复杂，暴力复杂度又过高，很难直接算出最终结果
逆向思维：把“求”转成“判”
2.2 第二步：大拆小小组大
大拆小：猜测一个答案 XXX，判断“最终询问位置上的数是否 ≥X\ge X≥X”
小组大：将 ≥X\ge X≥X 的和 <X< X<X 的分别记为 AAA 和 BBB。这时我们只需要把状态 AAA 放在一边，把状态 BBB 放在一边，统计一段区间中 AAA 的个数，就能知道排序后这段区间的样子。最后合并出大答案
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 最终代码（禁止抄袭，仅用于参考）
常错点：
pushdown正确逻辑：
* 判断是否有lazytag，若是:
下传懒标记
更新孩子的答案（如sum）
清空layztag
add,change,mul等函数:
* 若是叶子结点：
更新并return
pushdown
mid计算的应该是tree[i].l,tree[i].r的mid而非操作区间l,r的mid
递归时应判断l,r与mid的关系
并且当使用判断l,r与mid的关系时，一定要加上完全无重合的返回空
pushup
注意query的左右区间包含的判断条件（具体见【模板】线段树2与【模板】线段树1.5）
