考场没敢写Splay，写了暴力，结束了写了写Splay练手，结果都mle了，求大佬！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

inline int read() {
	int x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}

struct Node {
	int val, idx;
	Node(int v=0, int i=0) {
		this->val = v; this->idx = i;
	}
	bool operator< (Node x) const {
		return val != x.val ? val < x.val : idx < x.idx;
	}
	bool operator> (Node x) const {
		return val != x.val ? val > x.val : idx > x.idx;
	}
	bool operator== (Node x) const {
		return val == x.val && idx == x.idx;
	}
};

const int MAXN = 8e3 + 5005;

int n, q, tot, root;
int fa[MAXN], ch[MAXN][2], siz[MAXN], cnt[MAXN];
Node tree[MAXN], a[MAXN];

inline int type(int x) {
	return x == ch[fa[x]][1];
}

inline int maintain(int x) {
	siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}

inline int clear(int x) {
	tree[x].val = 0; tree[x].idx = 0;
	fa[x] = ch[x][0] = ch[x][1] = siz[x] = cnt[x] = 0;
}

inline void rotate(int x) {
	int y = fa[x], z = fa[y], t = type(x);
	ch[y][t] = ch[x][t^1];
	if (ch[x][t^1]) fa[ch[x][t^1]] = y;
	ch[x][t^1] = y; fa[y] = x; fa[x] = z;
	if (z) ch[z][y==ch[z][1]] = x;
	maintain(y); maintain(x);
}

inline void splay(int x, int rt=0) {
	for (int f=fa[x]; (f=fa[x])!=rt; rotate(x))
		if (fa[f] != rt) rotate(type(x) == type(f) ? f : x);
	if (!rt) root = x;
}

void insert(Node x) {
	if (!root) {
		root = ++tot; tree[tot] = x;
		cnt[tot]++; maintain(tot); return;
	}
	int cur = root, f = 0;
	while (1) {
		if (tree[cur] == x) {
			cnt[cur]++; maintain(cur);
			splay(tot); return; 
		}
		f = cur; cur = ch[cur][x>tree[cur]];
		if (!cur) {
			tot++; tree[tot] = x; cnt[tot]++;
			fa[tot] = f; ch[f][x>tree[f]] = tot;
			maintain(tot); splay(tot); return;
		}
	}
}

int getTreeID(Node x) {
	int cur = root;
	while (1) {
		if (tree[cur] == x) { 
			splay(cur); return cur;
		}
		cur = ch[cur][x>tree[cur]];
	}
	return -1;
}

int rank_of(Node x) {
	int cur = root, sum = 0;
	while (1) {
		if (x < tree[cur]) cur = ch[cur][0];
		else {
			sum += siz[ch[cur][0]];
			if (x == tree[cur]) {
				splay(cur); return sum + 1;
			}
			sum += cnt[cur]; cur = ch[cur][1];
		}
	}
	return -1;
}

int pre() {
	int cur = ch[root][0];
	while (ch[cur][1]) cur = ch[cur][1];
	splay(cur); return cur;
}

void delete_(Node x) {
	rank_of(x);
	if (cnt[root] > 1) {
		cnt[root]--; maintain(root); return;
	}
	if (!ch[root][0] && !ch[root][1]) {
		clear(root); root = 0; return;
	}
	int cur = root;
	if (!ch[cur][0]) {
		root = ch[cur][1]; fa[root] = 0;
		clear(cur); return; 
	}
	if (!ch[cur][1]) {
		root = ch[cur][0]; fa[root] = 0;
		clear(cur); return;
	}
	int newRt = pre();
	fa[ch[cur][1]] = root; ch[newRt][1] = ch[cur][1];
	clear(cur); maintain(newRt); return;
}

int main() {
//	freopen("sort.in", "r", stdin);
//	freopen("sort.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	n = read(); q = read();
	for (int i=1; i<=n; ++i) {
		a[i].val = read(); a[i].idx = i;
		insert(a[i]);
	}
	for (int i=1; i<=q; ++i) {
		int op = read(), x = read(), y;
		if (op == 1) {
			y = read(); delete_(a[x]);
			insert(a[x] = Node(y, a[x].idx));
		}
		else std::cout << rank_of(a[x]) << '\n';
	}
	return 0;
}