rt，样例的第九个数据开始出现问题，初步推测可能是findrk函数和父结点的维护出现问题

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

const int R = 2e5 + 100;
struct
{
	int lc, rc, key, sz, fa;
	int lb, rb;
} tree[R]; // 以排名为关键字的平衡树，lb、rb记录的是用户编号
int tot, root;
mt19937 rd;
map<int, int> mp; // 以编号为关键字的平衡树
// first:leftbound
// second:node
int crt(int l, int r)
{
	tree[++tot].sz = r - l + 1;
	tree[tot].lb = l;
	tree[tot].rb = r;
	tree[tot].key = rd();
	mp[l] = tot;
	return tot;
}
#define lc(k) tree[k].lc
#define rc(k) tree[k].rc
#define len(k) (tree[k].rb - tree[k].lb + 1)
#define fa(k) tree[k].fa
void pushup(int k)
{
	tree[k].sz = tree[lc(k)].sz + tree[rc(k)].sz + len(k);
	tree[lc(k)].fa = tree[rc(k)].fa = k; // 将父结点和子结点互相连接上（因为如果没有这句就只是父结点连接子结点）
}
int merge(int x, int y)
{
	if (!x || !y)
		return x + y;
	if (tree[x].key < tree[y].key)
	{
		tree[x].rc = merge(tree[x].rc, y);
		pushup(x);
		return x;
	}
	else
	{
		tree[y].lc = merge(x, tree[y].lc);
		pushup(y);
		return y;
	}
}
void splitnode(int k, int sz)
{
	if (len(k) <= sz)
		return; // 如果当前结点不够分裂出新结点，或者本身节点大小就是sz，就直接返回
	int r1 = tree[k].lb + sz - 1;
	int newnode = crt(r1 + 1, tree[k].rb);
	// tree[newnode].key = tree[k].key; // 强制维护堆的性质，不写也行
	tree[k].rb = r1;
	tree[k].rc = merge(newnode, tree[k].rc);
	pushup(k), pushup(rc(k));
}
void split(int k, int sz, int &x, int &y)
{
	if (k == 0)
	{
		x = y = 0;
		return;
	}
	if (tree[lc(k)].sz >= sz)
	{
		y = k;
		split(tree[y].lc, sz, x, tree[y].lc);
	}
	else
	{
		x = k;
		splitnode(x, sz - tree[lc(k)].sz);
		split(tree[x].rc, sz - tree[lc(k)].sz - len(k), tree[x].rc, y);
	}
	pushup(k);
}
int findrk(int id) // 查找左边界的左边还有多少个用户
{
	int x = id, res = 0;
	while (x != root && fa(x) != 0)
	{
		if (rc(fa(x)) == x) // 当前结点是一个右儿子
			res += tree[lc(fa(x))].sz + len(fa(x));
		x = fa(x);
	}
	return res;
}
int a, b, c;
int update(int x, int y)
{
	int id = (--mp.upper_bound(x))->second;
	int rk = findrk(id);
	split(root, rk + x - tree[id].lb, a, b);
	split(b, 1, b, c);
	tree[b].lb = tree[b].rb = y; // 改编号
	mp[y] = b;
	root = merge(merge(a, b), c);
	// int res = rk + x - tree[id].lb + 1;
	// int res = findrk(b);
	return findrk(b) + 1;
}
int tof(int x)
{
	// auto it = --mp.upper_bound(x);
	// int lb = it->first, id = it->second;
	// int rb = tree[id].rb;
	// int res = findrk(id) - (rb - x);

	int id = (--mp.upper_bound(x))->second;
	// cout << '\n'
	// 	 << id << '\n';
	int rk = findrk(id);
	// cout << 'n' << rk;
	split(root, rk + x - tree[id].lb, a, b);
	split(b, 1, b, c);
	// mp[x] = b;
	int res = tree[a].sz + 1;
	root = merge(merge(b, a), c);
	return res;
}
int tol(int x)
{
	int id = (--mp.upper_bound(x))->second;
	int rk = findrk(id);
	split(root, rk + x - tree[id].lb, a, b);
	// cout << '\n'
	// 	 << 'r' << id << '\n';
	split(b, 1, b, c);
	// mp[x] = b;
	int res = tree[a].sz + 1;
	root = merge(merge(a, c), b);
	return res;
}
int kth(int k)
{
	int x = root, res;
	while (x)
	{
		if (tree[lc(x)].sz + 1 == k)
		{
			res = tree[k].lb;
			break;
		}
		if (tree[lc(x)].sz >= k)
			x = lc(x);
		else
		{
			k -= tree[lc(x)].sz;
			if (k > len(x))
			{
				k -= len(x);
				x = rc(x);
			}
			else
			{
				splitnode(x, k - 1);
				x = rc(x);
			}
		}
	}
	return res;
}
int t;
void print(int x)
{
	if (lc(x))
		print(lc(x));
	// cout << '\n';
	++t;
	for (int j = tree[x].lb; j <= tree[x].rb; ++j)
		cout << j << ' ';
	// cout << '\n';
	if (rc(x))
		print(rc(x));
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, opt, x, y, ans = 0;
	cin >> n >> m;
	root = crt(1, n);
	for (int j = 1; j <= m; ++j)
	{
		cin >> opt >> x;
		if (opt == 1)
		{
			cin >> y;
			x -= ans, y -= ans;
			ans = update(x, y);
		}
		else if (opt == 2)
		{
			x -= ans;
			ans = tof(x);
		}
		else if (opt == 3)
		{
			x -= ans;
			ans = tol(x);
		}
		else
		{
			x -= ans;
			ans = kth(x);
		}
		cout << ans << '\n';
	}
	// cout << endl
	// 	 << endl
	// 	 //  << tree[2].lb << tree[2].rb;
	// 	 //  << (--mp.end())->first << endl;
	// 	 << mp[8];
	// cout << endl
	// 	 << mp.size()
	// 	 << endl
	// 	 << endl;
	// cout << tot << ' ';
	// print(root);
	// cout << '\n';
	// cout << t;
	// print(root);
	// for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
	// {
	// 	cout << it->first << ' ' << it->second << '\n';
	// }
	// for (int j = 1; j <= tot; ++j)
	// {
	// 	cout << tree[j].lb << ' ' << tree[j].rb << '\n';
	// }
	return 0;
}