RT,WA on #2

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int sum = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * f; 
}
void write(int x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar('0' + x % 10);
	return;
}
const int N = 1e5 + 10,
		  D = 3;
int n, m, q;
int cnt, fa[N * D], c[N * D][2], val[N * D];
map<int, int> mp;
struct node{
	int x, id;
	node(int x = 0, int id = 0) : x(x), id(id) {}
	bool operator < (const node &b) const{
		return this -> x < b.x;
	}
};
set<node> S[N];
set<node> :: iterator it;
struct SPLAY{
	int rt;
	SPLAY(int rt = 0) : rt(rt) {}
	int New(int v, int f = 0){
		int p = ++ cnt;
		val[p] = v;
		c[p][0] = c[p][1] = 0;
		fa[p] = f;
		return p;
	}
	void rotate(int x){
		int y = fa[x], z = fa[y];
		bool k = (c[y][0] == x);
		if(z) c[z][c[z][1] == y] = x;
		else rt = x;
		fa[x] = z;
		c[y][k ^ 1] = c[x][k], fa[c[x][k]] = y;
		c[x][k] = y, fa[y] = x;
		return;
	}
	void Splay(int x, int goal = 0){
		while(fa[x] != goal){
			int y = fa[x], z = fa[y];
			if(z != goal) (c[z][0] == y) ^ (c[y][0] == x) ? rotate(x) : rotate(y);
			rotate(x);
		}
		if(!goal) rt = x;
		return;
	}
	int find(int k){
		int p = rt;
		while(p){
			if(val[p] == k) return p;
			if(k < val[p]) p = c[p][0];
			else p = c[p][1];
		}
		Splay(p);
		return p;
	}
	int find_pre(int k){//找前驱
		int p = rt, res = -1;
		while(p){
			if(val[p] < k) res = p, p = c[p][1];
			else p = c[p][0];
		}
		Splay(res);
		return res;
	}
	void insert(int k){
		int *p = &rt, f = 0;
		while(*p){
			f = *p;
			if(k < val[*p]) p = &c[*p][0];
			else if(k == val[*p]) return;
			else p = &c[*p][1];
		}
		*p = New(k, f);
		Splay(*p);
		return;
	}
}tr[N];
void gs(int p){
	if(!p) return;
	gs(c[p][0]);
	cout << val[p] << " ";
	gs(c[p][1]);
	return;
}
void out(int id){
	for(it = S[id].begin(); it != S[id].end(); ++ it)
		cout << "{" << (*it).x << " " << (*it).id << "} ";
	cout << "\n";
	return;
}
signed main(){
	n = read(), m = read(), q = read();
	for(int i = 1; i <= n; ++ i){
		tr[i].insert(0);
		tr[i].insert(m + 1);
		mp[tr[i].find(m + 1)] = i;
		S[i].insert(node(0, i));
	}
	int op, u, v, ta, tb, tmpa, tmpb;
	while(q --){
		op = read();
		if(op == 1){
			u = read(), v = read();
			it = S[u].upper_bound(node(v)), 	ta = (*-- it).id;
			it = S[u + 1].upper_bound(node(v)), tb = (* --it).id;
			S[u].insert(node(v, tb));
			S[u + 1].insert(node(v, ta));
			// cout << "real root: " << ta << " " << tb << "\n";
			tr[ta].insert(v), tr[tb].insert(v);
			tmpa = tr[ta].find_pre(v), tmpb = tr[tb].find_pre(v);
			tr[ta].Splay(tmpa), tr[tb].Splay(tmpb);
			swap(c[tmpa][1], c[tmpb][1]);
			fa[c[tmpa][1]] = tmpa;
			fa[c[tmpb][1]] = tmpb;
		}else if(op == 2){
			u = read();
			write(mp[tr[u].find(m + 1)]);
			puts("");
		}
		// cout << "tree:\n";
		// for(int i = 1; i <= n; ++ i){
		// 	gs(tr[i].rt), cout << "ans: " << mp[tr[i].find(m + 1)];
		// 	cout << "\n";
		// }
		// cout << "id:\n";
		// for(int i = 1; i <= n; ++ i){
		// 	out(i);
		// 	puts("");
		// }
	}
	return 0;
}
/*
2 10 10
2 1
2 2
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
2 1
2 2
*/