RT

一开始的时候甚至会输出原本加入的数中不存在的信息

后来改成在排好序的数组中二分下标，上面的问题解决了，但是还是 WA 18，求助

#include <bits/stdc++.h>

#define LL long long

using namespace std;

template <typename Temp> void read(Temp & res) {
	Temp fh = 1; res = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
	res = res * fh; 
}

using namespace std;

const int Maxn = 5e4 + 5;
 
int n, m, cnt;
 
struct Segment_Tree {
	#define ls t << 1
	#define rs t << 1 | 1 
	struct Unit {
		LL data, tag;
		Unit() {data = tag = 0;}
	} a[Maxn << 2];
	void pushup(int t) {a[t].data = a[ls].data + a[rs].data;}
	void pushdown(int l, int r, int t) {
		int mid = (l + r) >> 1; LL tg = a[t].tag; a[t].tag = 0;
		a[ls].data += tg * (mid - l + 1); a[ls].tag += tg;
		a[rs].data += tg * (r - mid); a[rs].tag += tg;
	}
	void modify(int lf, int rt, LL x, int l, int r, int t) {
		if(lf <= l && r <= rt)  {
			a[t].data += (r - l + 1) * x;
			a[t].tag += x; return;
		}
		int mid = (l + r) >> 1; pushdown(l, r, t);
		if(lf <= mid) modify(lf, rt, x, l, mid, ls); 
		if(mid < rt) modify(lf, rt, x, mid + 1, r, rs);
		pushup(t);
	}
	LL query(int lf, int rt, int l, int r, int t) {
		if(lf <= l && r <= rt) return a[t].data;
		int mid = (l + r) >> 1; LL res = 0; pushdown(l, r, t);
		if(lf <= mid) res += query(lf, rt, l, mid, ls);
		if(mid < rt) res += query(lf, rt, mid + 1, r, rs);
		return res;
	}
	#undef ls
	#undef rs
} s;

int ql[Maxn], qr[Maxn], typ[Maxn], qid[Maxn];
LL qk[Maxn], p[Maxn];
int tml[Maxn], tmr[Maxn], ans[Maxn];

void solve(LL l, LL r, int lf, int rt) {
	if(l == r) {
		for(int i = lf; i <= rt; ++i) if(typ[qid[i]] == 2) ans[qid[i]] = p[l];
		return;
	}
	LL mid = (l + r) >> 1;
	int tl = 0, tr = 0; bool wl = 0, wr = 0;
	for(int i = lf; i <= rt; ++i) {
		if(typ[qid[i]] == 2) {
			LL res = s.query(ql[qid[i]], qr[qid[i]], 1, n, 1);
			if(res >= qk[qid[i]]) tmr[++tr] = qid[i], wr = 1;
			else tml[++tl] = qid[i], wl = 1;
		} else {
			if(qk[qid[i]] > p[mid]) {
				s.modify(ql[qid[i]], qr[qid[i]], 1, 1, n, 1);
				tmr[++tr] = qid[i];
			} else tml[++tl] = qid[i];
		}
	}
	for(int i = lf; i <= rt; ++i)
		if(typ[qid[i]] == 1)
			if(qk[qid[i]] > p[mid])
				s.modify(ql[qid[i]], qr[qid[i]], -1, 1, n, 1);
	for(int i = 1; i <= tl; ++i) qid[lf + i - 1] = tml[i];
	for(int i = 1; i <= tr; ++i) qid[lf + tl + i - 1] = tmr[i];
	if(wl) solve(l, mid, lf, lf + tl - 1);
	if(wr) solve(mid + 1, r, lf + tl, lf + tl + tr - 1);
}

int main() {
	read(n); read(m);
	for(int i = 1; i <= m; ++i) {
		read(typ[i]); read(ql[i]); read(qr[i]); read(qk[i]); qid[i] = i;
		if(typ[i] == 1) p[++cnt] = qk[i];
	}
	sort(p + 1, p + cnt + 1);
	solve(1, cnt, 1, m);
	for(int i = 1; i <= m; ++i) {
		if(typ[i] == 2) {
			printf("%d\n", ans[i]);
		}
	}
	return 0;
}