まず、得点について大事なのは大小関係だけであってその差分は関係が無い事から、座標圧縮の要領で登場する得点を小さい方から順に\(0\), \(1\), \(\ldots\) としても答えは変わりません。このとき、得点は \(0\) 以上 \(N+Q\) 以下の整数値を取ります。

各選手の得点はつねにすべて異なりますから、現在 \(x\) 点の選手、というのは存在すれば一意に定まります。よって、そのクエリの時点での選手 \(a\) の得点を \(A_a\) 、得点が \(x\) の選手を \(B_x\) として、クエリは次のように書き換えられます。

• 1 a x : 得点 \(A_a\) の選手が消え、新たに得点 \(x\) の選手が追加される。この得点 \(x\) の選手には選手番号 \(a\) が割り当てられる。
• 2 a : 得点が \(A_a\) 以上の選手は何人いるか出力せよ。
• 3 r : 得点が \(x\) 以上の選手が \(r\) 人以上いる最大の \(x\) に対して、\(B_x\) を出力せよ。

これは \(i\) 番目の要素が得点 \(i\) の選手の人数を表すセグメント木によって、管理する事ができ、それぞれのクエリに対して \(O(\log (N+Q))\) で答えを出すことができます。 また、\(A_a, B_x\) は配列をクエリに合わせて更新する事で求まります。よって、 \(O(N+Q\log (N+Q))\) でこの問題を解く事が出来ました。BITによって解くこともできます。

c++による実装例 (ACLを用いたもの) :

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

#define MAX_N 500010
#define MAX_Q 500010

int op(int a, int b) { return a + b; }

int e() { return 0; }

int target;

bool f(int v) { return v < target; }

int main() {
	int n, q, s;

    cin >> n >> q;

	vector<int>comp;
	vector<int>cur(n);
	vector<int>qt(q);
	vector<int>qa(q);
	vector<int>qx(q);

	for (int i = 0; i < n; i++) {
		cin >> cur[i];
		comp.push_back(cur[i]);
	}

	for (int i = 0; i < q; i++) {
		cin >> qt[i];
		if (qt[i] == 1) {
			cin >> qa[i] >> qx[i];
			qa[i]--;
			comp.push_back(qx[i]);
		}
		else if (qt[i] == 2) {
			cin >> qa[i];
			qa[i]--;
		}
		else cin >> qa[i];
	}

	sort(comp.begin(), comp.end());
	int sz = comp.size();
	map<int, int>mp;
	vector<int>rev(sz);

	for (int i = 0; i < sz; i++)mp[comp[i]] = i;

	vector<int>init(sz);

	for (int i = 0; i < n; i++) {
		init[mp[cur[i]]] = 1;
		rev[mp[cur[i]]] = i + 1;
	}

	segtree<int, op, e> seg(init);

	for (int i = 0; i < q; i++) {
		if (qt[i] == 1) {
			seg.set(mp[cur[qa[i]]], 0);
			cur[qa[i]] = qx[i];
			rev[mp[qx[i]]] = qa[i] + 1;
			seg.set(mp[cur[qa[i]]], 1);
		}
		else if (qt[i] == 2) {
			cout << seg.prod(mp[cur[qa[i]]], sz) << endl;
		}
		else {
			target = qa[i];
			cout << rev[seg.min_left<f>(sz)-1] << endl;
		}
	}
	return 0;
}

c++による実装例 (ACLを用いないもの) :

#include <bits/stdc++.h>
using namespace std;

#define N (1<<20)
int seg[2 * N];

void update(int k, int x) {
	k += N;
	seg[k] = x;
	while (k > 1) {
		k = (k >> 1);
		seg[k] = seg[(k << 1)] + seg[((k << 1) | 1)];
	}
	return;
}

int sum(int l) {
	int ll = 0;
	int rr = N;
	int k = 1;
	int s = 0;
	while (k < N) {
		if (l < ((ll + rr) / 2)) {
			s += seg[(2 * k) + 1];
			rr = (ll + rr) / 2;
			k = 2 * k;
		}
		else {
			ll = (ll + rr) / 2;
			k = 2 * k + 1;
		}
	}
	return (s + seg[k]);
}

int min_left(int target) {
	int k = 1;
	while (k < N) {
		if (seg[2 * k + 1] < target) {
			target -= seg[2 * k + 1];
			k = 2 * k;
		}
		else k = 2 * k + 1;
	}
	return (k - N);
}

int main() {
	int n, q, s;

	cin >> n >> q;

	vector<int>comp;
	vector<int>cur(n);
	vector<int>qt(q);
	vector<int>qa(q);
	vector<int>qx(q);

	for (int i = 0; i < n; i++) {
		cin >> cur[i];
		comp.push_back(cur[i]);
	}

	for (int i = 0; i < q; i++) {
		cin >> qt[i];
		if (qt[i] == 1) {
			cin >> qa[i] >> qx[i];
			qa[i]--;
			comp.push_back(qx[i]);
		}
		else if (qt[i] == 2) {
			cin >> qa[i];
			qa[i]--;
		}
		else cin >> qa[i];
	}

	sort(comp.begin(), comp.end());
	int sz = comp.size();
	map<int, int>mp;
	vector<int>rev(sz);
	for (int i = 0; i < sz; i++)mp[comp[i]] = i;

	for (int i = 0; i < (2*N); i++)seg[i] = 0;
	for (int i = 0; i < n; i++) {
		update(mp[cur[i]], 1);
		rev[mp[cur[i]]] = i + 1;
	}

	for (int i = 0; i < q; i++) {
		if (qt[i] == 1) {
			update(mp[cur[qa[i]]], 0);
			cur[qa[i]] = qx[i];
			rev[mp[qx[i]]] = qa[i] + 1;
			update(mp[cur[qa[i]]], 1);
		}
		else if (qt[i] == 2) cout << sum(mp[cur[qa[i]]]) << endl;
		else cout << rev[min_left(qa[i])] << endl;
	}
	return 0;
}