求区间升序或降序第K大的数

地址（现在qscoj好像挂了）
询问只有一次，可以二分答案。对于答案x来说，这个序列只有大于x的和小于等于的。
如果第[1, k]上比x小的数小于k则可以l = mid,否则r = mid;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int cc[400010];
struct P{
	int f, l, r;
};
P b[100010];
struct node{
	int l, r;
	int one, zero;
	int lazy;
	int size(){return (r-l+1);}
	int mid() {return (l+r)/2;}
}tr[maxn<<2];
void pushup(int rt) {
	tr[rt].zero = tr[rt<<1].zero + tr[rt<<1|1].zero;
	tr[rt].one = tr[rt<<1].one + tr[rt<<1|1].one;
}
void pushdown(int rt) {
	if(~tr[rt].lazy) {
		tr[rt<<1].lazy = tr[rt<<1|1].lazy = tr[rt].lazy;
		if(tr[rt].lazy) {
			tr[rt<<1].one = tr[rt<<1].size();
			tr[rt<<1|1].one = tr[rt<<1|1].size();
			tr[rt<<1].zero = 0;
			tr[rt<<1|1].zero = 0;
		}
		else {
			tr[rt<<1].zero = tr[rt<<1].size();
			tr[rt<<1|1].zero = tr[rt<<1|1].size();
			tr[rt<<1].one = 0;
			tr[rt<<1|1].one = 0;
		}
		tr[rt].lazy = -1;
	}
}
void build(int rt, int l, int r, int val) {
	tr[rt].l = l; tr[rt].r = r;
	tr[rt].lazy = -1;
	if(l == r) {
		if(cc[l] < val) tr[rt].zero = 1, tr[rt].one = 0;
		else tr[rt].one = 1, tr[rt].zero = 0;
		return;
	}
	int mid = tr[rt].mid();
	build(rt<<1, l, mid, val);
	build(rt<<1|1, mid+1, r, val);
	pushup(rt);
}
void update(int rt ,int l, int r, int c) {
	if(tr[rt].l == l && tr[rt].r == r) {
		if(c) {
			tr[rt].zero = 0;
			tr[rt].one = tr[rt].size();
		}
		else {
			tr[rt].zero = tr[rt].size();
			tr[rt].one = 0;
		}
		tr[rt].lazy = c;
		return;
	}
	pushdown(rt);
	int mid = tr[rt].mid();
	if(r <= mid) update(rt<<1, l, r, c);
	else if(l > mid) update(rt<<1|1, l, r, c);
	else update(rt<<1, l, mid, c), update(rt<<1|1, mid+1, r, c);
	pushup(rt);
}
int query(int rt ,int l, int r, int c) {
	if(tr[rt].l == l && tr[rt].r == r) {
		if(c) return tr[rt].one;
		else return tr[rt].zero;
	}
	pushdown(rt);
	int mid = tr[rt].mid();
	if(r <= mid) return query(rt<<1, l, r, c);
	else if(l > mid)return query(rt<<1|1, l, r, c);
	else return query(rt<<1, l, mid, c)+query(rt<<1|1, mid+1, r, c);
}
int que(int rt, int pos) {
	if(tr[rt].l == tr[rt].r) {
		return tr[rt].one;
	}
	int mid = tr[rt].mid();
	pushdown(rt);
	if(pos <= mid) return que(rt<<1, pos);
	else return que(rt<<1|1, pos);
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &cc[i]);
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
		scanf("%d%d%d", &b[i].f, &b[i].l, &b[i].r);
	int l = 1, r = n+1;
	while (l < r-1) {
		int mm = (l+r)/2;
		build(1, 1, n, mm);
		for (int i = 0; i < q; i++) {
			int u = b[i].f;
			int one = query(1, b[i].l, b[i].r, 1), zo = (b[i].r-b[i].l+1)-one;
			if (one == 0 || zo == 0) continue;
			if (u == 0) {
				int x = b[i].l;
				int y = b[i].l+zo-1;
				update(1, x, y, 0);
				x = b[i].l+zo;
				y = b[i].r;
				update(1, x, y, 1);
			}
			else {
				int x = b[i].l;
				int y = b[i].l+one-1;
				update(1, x, y, 1);
				x = b[i].l+one;
				y = b[i].r;
				update(1, x, y, 0);
			}
		}
		if (que(1, m)) l = mm;
		else r = mm;
	}
	printf("%d\n", l);
	return 0;
}