Description
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题
，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排
序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q
位置上的数字。
Input
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整
数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序
排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5
，1 <= m <= 10^5
Output
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
题解（转载）
首先常规套路，如果值域较小，那么枚举值域线段树区间覆盖
那么这题这么做这个转换呢？直接二分答案，把小于的部分赋为$0$，大于等于部分$1$，这样转换过来了，注意线段树只要存$1$就好,$0$直接可以相减得出
//It is made by Awson on 2017.10.23
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Lr(o) (o<<1)
#define Rr(o) (o<<1|1)
using namespace std;
const int N = 1e5; int n, m, q, a[N+];
struct operat {
int opt, l, r;
}p[N+];
struct tt {
int sgm[(N<<)+], lazy[(N<<)+];
void build(int o, int l, int r, int key) {
lazy[o] = ;
if (l == r) {
sgm[o] = (a[l]>=key); return;
}
int mid = (l+r)>>;
build(Lr(o), l, mid, key); build(Rr(o), mid+, r, key);
sgm[o] = sgm[Lr(o)]+sgm[Rr(o)];
}
void pushdown(int o, int l, int r, int mid) {
if (lazy[o] == ) {
lazy[Lr(o)] = lazy[Rr(o)] = ;
sgm[Lr(o)] = mid-l+, sgm[Rr(o)] = r-mid;
lazy[o] = ;
}else if (lazy[o] == -) {
lazy[Lr(o)] = lazy[Rr(o)] = -;
sgm[Lr(o)] = , sgm[Rr(o)] = ;
lazy[o] = ;
}
}
void update(int o, int l, int r, int a, int b, int key) {
if (a <= l && r <= b) {
if (key) lazy[o] = , sgm[o] = r-l+;
else lazy[o] = -, sgm[o] = ;
return;
}
int mid = (l+r)>>;
pushdown(o, l, r, mid);
if (a <= mid) update(Lr(o), l, mid, a, b, key);
if (mid < b) update(Rr(o), mid+, r, a, b, key);
sgm[o] = sgm[Lr(o)]+sgm[Rr(o)];
}
int query(int o, int l, int r, int a, int b) {
if (a <= l && r <= b) return sgm[o];
int mid = (l+r)>>;
pushdown(o, l, r, mid);
int ca = , cb = ;
if (a <= mid) ca = query(Lr(o), l, mid, a, b);
if (mid < b) cb = query(Rr(o), mid+, r, a, b);
return ca+cb;
}
}T; bool judge(int x) {
T.build(, , n, x);
int l, r, cnt0, cnt1;
for (int i = ; i <= m; i++) {
l = p[i].l, r = p[i].r;
cnt1 = T.query(, , n, l, r); cnt0 = r-l+-cnt1;
if (p[i].opt == ) {
if (cnt0 != ) T.update(, , n, l, l+cnt0-, );
if (cnt1 != ) T.update(, , n, l+cnt0, r, );
}else {
if (cnt1 != ) T.update(, , n, l, l+cnt1-, );
if (cnt0 != ) T.update(, , n, l+cnt1, r, );
}
}
return T.query(, , n, q, q) == ;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i <= m; i++) scanf("%d%d%d", &p[i].opt, &p[i].l, &p[i].r);
scanf("%d", &q);
int l = , r = n, ans;
while (l <= r) {
int mid = (l+r)>>;
if (judge(mid)) l = mid+, ans = mid;
else r = mid-;
}
printf("%d\n", ans);
}
int main() {
work();
return ;
}