传送门：点击打开链接
题意：一个n的排列，然后执行Q次操作，每次操作是对某个区间从小到大排序或者是从大到小排序。最后只查询一次，输出第k个位置当前的数。
思路：这道题最特别的地方，就是，只查询了1次，因为这个特点也让这道题有了不同寻常的解法。
我们可以直接二分第k个位置的数的大小记为m，然后给初始序列处理一下，把小于等于m的记为0，大于m的记为1
之后的排序操作就非常简单了，只需要区间修改，区间查询，就能完成了，就是把区间里面所有的1移动到最前面或者是最后面。
因为假如我枚举了m后，其他数字的状态就瞬间减少了，只有比m小，比m大这两种概念了！
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <Stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1int n, pos, Q;
int op[MX][3];
int S[MX << 2], col[MX << 2], A[MX];void push_up(int rt) {S[rt] = S[rt << 1] + S[rt << 1 | 1];
}
void push_down(int rt, int m, int len) {if(col[rt] != -1) {int szr = len >> 1, szl = len - szr;col[rt << 1] = col[rt << 1 | 1] = col[rt];S[rt << 1] = szl * col[rt]; S[rt << 1 | 1] = szr * col[rt];col[rt] = -1;}
}
void build(int x, int l, int r, int rt) {col[rt] = -1;if(l == r) {S[rt] = A[l] <= x ? 0 : 1;return;}int m = (l + r) >> 1;build(x, lson); build(x, rson);push_up(rt);
}
int query(int L, int R, int l, int r, int rt) {if(L <= l && r <= R) {return S[rt];}int ret = 0, m = (l + r) >> 1;push_down(rt, m, r - l + 1);if(L <= m) ret += query(L, R, lson);if(R > m) ret += query(L, R, rson);return ret;
}
void update(int L, int R, int x, int l, int r, int rt) {if(L > R) return;if(L <= l && r <= R) {col[rt] = x;S[rt] = (r - l + 1) * x;return;}int m = (l + r) >> 1;push_down(rt, m, r - l + 1);if(L <= m) update(L, R, x, lson);if(R > m) update(L, R, x, rson);push_up(rt);
}
void print(int l, int r, int rt) {if(l == r) {fuck(S[rt]);return;}int m = (l + r) >> 1;push_down(rt, m, r - l + 1);print(lson); print(rson);
}
bool check(int x) {build(x, 1, n, 1);for(int i = 1; i <= Q; i++) {int sum = query(op[i][1], op[i][2], 1, n, 1);if(op[i][0] == 0) {update(op[i][1], op[i][2] - sum, 0, 1, n, 1);update(op[i][2] - sum + 1, op[i][2], 1, 1, n, 1);} else {update(op[i][1], op[i][1] + sum - 1, 1, 1, n, 1);update(op[i][1] + sum, op[i][2], 0, 1, n, 1);}}int w = query(pos, pos, 1, n, 1);return w == 0;
}
int main() {int T; //FIN;scanf("%d", &T);while(T--) {scanf("%d%d", &n, &Q);for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);}for(int i = 1; i <= Q; i++) {for(int j = 0; j < 3; j++) {scanf("%d", &op[i][j]);}}scanf("%d", &pos);int l = 1, r = n, m;while(l <= r) {m = (l + r) >> 1;if(check(m)) r = m - 1;else l = m + 1;}printf("%d\n", r + 1);}return 0;
}