RT，本蒟蒻写的是带修莫队，样例 AC，但全部 WA /kk

代码：

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef struct {
	int pos;
	int val;
} Modification;

typedef struct {
	int id;
	int opt;
	int l;
	int r;
	int time;
	int k;
} Query;

int block1;
int a[50007], b[100007], belong[100007], lft[327], rt[327], cnt[100007], sum[327], ans[50007];
Modification modification[50007];
Query query[50007];

bool operator <(const Query a, const Query b){
	if (a.l / block1 != b.l / block1) return a.l < b.l;
	if (a.r / block1 != b.r / block1) return a.r < b.r;
	return a.time < b.time;
}

inline void add(int x){
	cnt[x]++;
	sum[belong[x]]++;
}

inline void del(int x){
	cnt[x]--;
	sum[belong[x]]--;
}

inline void modify(int x, int time){
	if (query[x].l <= modification[time].pos && modification[time].pos <= query[x].r){
		del(a[modification[time].pos]);
		add(modification[time].val);
	}
	swap(a[modification[time].pos], modification[time].val);
}

inline int brute_force_get_sum(int l, int r){
	int ans = 0;
	for (register int i = l; i <= r; i++){
		ans += cnt[i];
	}
	return ans;
}

inline int get_sum(int l, int r){
	int ans = brute_force_get_sum(l, min(r, rt[belong[l]]));
	if (belong[l] != belong[r]) ans += brute_force_get_sum(lft[belong[r]], r);
	for (register int i = belong[l] + 1; i < belong[r]; i++){
		ans += sum[i];
	}
	return ans;
}

inline int get_kth_number(int k, int n){
	if (k <= 0 || k > get_sum(1, n)) return -1;
	int l = 1, r = n, ans;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (get_sum(1, mid) >= k){
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	return ans;
}

inline int get_prev(int k, int n){
	return get_kth_number(get_sum(1, k - 1), n);
}

inline int get_next(int k, int n){
	return get_kth_number(get_sum(1, k) + 1, n);
}

int main(){
	int n, m, block2, modification_cnt = 0, val_cnt, k, query_cnt = 0;
	cin >> n >> m;
	val_cnt = n;
	for (register int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	for (register int i = 1; i <= m; i++){
		int opt;
		cin >> opt;
		if (opt == 3){
			modification_cnt++;
			cin >> modification[modification_cnt].pos >> modification[modification_cnt].val;
			b[++val_cnt] = modification[modification_cnt].val;
		} else {
			query_cnt++;
			query[query_cnt].opt = opt;
			cin >> query[query_cnt].l >> query[query_cnt].r >> query[query_cnt].k;
			query[query_cnt].id = query_cnt;
			query[query_cnt].time = modification_cnt;
			if (opt != 2) b[++val_cnt] = query[query_cnt].k;
		}
	}
	block1 = ceil(n / cbrt(query_cnt));
	sort(b + 1, b + val_cnt + 1);
	val_cnt = unique(b + 1, b + val_cnt + 1) - b - 1;
	block2 = sqrt(val_cnt);
	k = (val_cnt - 1) / block2 + 1;
	for (register int i = 1; i <= n; i++){
		a[i] = lower_bound(b + 1, b + val_cnt + 1, a[i]) - b;
	}
	for (register int i = 1; i <= modification_cnt; i++){
		modification[i].val = lower_bound(b + 1, b + val_cnt + 1, modification[i].val) - b;
	}
	for (register int i = 1; i <= query_cnt; i++){
		if (query[i].opt != 2) query[i].k = lower_bound(b + 1, b + val_cnt + 1, query[i].k) - b;
	}
	for (register int i = 1; i <= val_cnt; i++){
		belong[i] = (i - 1) / block2 + 1;
	}
	for (register int i = 1; i <= k; i++){
		lft[i] = (i - 1) * block2 + 1;
		rt[i] = min(i * block2, val_cnt);
	}
	sort(query + 1, query + query_cnt + 1);
	for (register int i = 1, j = 1, x = 0, y = 0; i <= query_cnt; i++){
		while (j > query[i].l) add(a[--j]);
		while (x < query[i].r) add(a[++x]);
		while (j < query[i].l) del(a[j++]);
		while (x > query[i].r) del(a[x--]);
		while (y < query[i].time) modify(i, ++y);
		while (y > query[i].time) modify(i, y--);
		if (query[i].opt == 1){
			ans[query[i].id] = get_sum(1, query[i].k);
		} else if (query[i].opt == 2){
			ans[query[i].id] = b[get_kth_number(query[i].k, val_cnt)];
		} else if (query[i].opt == 4){
			int pos = get_prev(query[i].k, val_cnt);
			ans[query[i].id] = pos == -1 ? -0x7fffffff : b[pos];
		} else {
			int pos = get_next(query[i].k, val_cnt);
			ans[query[i].id] = pos == -1 ? 0x7fffffff : b[pos];
		}
	}
	for (register int i = 1; i <= query_cnt; i++){
		cout << ans[i] << endl;
	}
	return 0;
}