我用的是 $FHQ$，在根据排名查编号的函数 $getid(p, k)$ 中，我原本写的是下面这个：

int getid(int p, int k) {
    if (siz[ls[p]] >= k) return getid(ls[p], k);
    k -= siz[ls[p]];
    if (k <= len(p)) return l[p] + k - 1;
    return getid(rs[p], k - len(p));
}

但是这样写会 $TLE$，原因是 $p$ 会在递归后变成 $0$，进而导致死循环。

如果加上这句：if (!p) return 1;，那就可以 $AC$。

我在看其他人的题解时，发现别人好像没有这个问题，求原因。

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 7;

int n, m;
map<int, int> mp;
struct FHQ {
	int rt, nds;
	int fa[maxn], ls[maxn], rs[maxn];
	int siz[maxn], l[maxn], r[maxn];
	int pri[maxn];
	#define len(p) (r[p] - l[p] + 1)
	
	void print(int p) {
		if (!p) return ;
		printf("p:%d, l:%d, r:%d, siz:%d, pri:%d, ls:%d, rs:%d, fa:%d, mp[l:%d]:%d\n",
				p,    l[p], r[p], siz[p], pri[p], ls[p], rs[p], fa[p], l[p], mp[l[p]]);
		print(ls[p]), print(rs[p]);
	}
	
	void pushup(int p) {
		siz[p] = siz[ls[p]] + siz[rs[p]] + len(p);
		fa[ls[p]] = fa[rs[p]] = p;
	}
	void split(int p, int k, int& x, int& y) {
//		puts("Die in split.");
		if (!p) {x = y = 0; return ;}
		if (siz[ls[p]] + len(p) <= k) {
			x = p, split(rs[p], k - siz[ls[p]] - len(p), rs[x], y);
		} else {
			y = p, split(ls[p], k, x, ls[y]); 
		}
		pushup(p);
	}
	int merge(int x, int y) {
//		puts("Die in merge.");
		if (!x || !y) return x + y;
		if (pri[x] < pri[y]) {
			rs[x] = merge(rs[x], y);
			pushup(x); return x;
		} else {
			ls[y] = merge(x, ls[y]);
			pushup(y); return y;
		}
	}
	
	// 在排名为 pos 的位置上插入值域在 [L, R] 内的数 
	void insert(int pos, int L, int R) {
		int x, y;
		split(rt, pos - 1, x, y);
		mp[L] = ++nds;
		pri[nds] = rand();
		siz[nds] = R - L + 1;
		l[nds] = L, r[nds] = R;
		rt = merge(merge(x, nds), y);
//		fa[rt] = 0;  // 将新根的父亲设为 0 
	}
	
	// 删除排名在 [L, R] 的数 
	void erase(int L, int R) {
//		puts("-------------------------------");
//		puts("In erase");
		int x, y, z;
		split(rt, R, x, z);
//		printf("[1, R:%d]:\n", R);
//		print(x);
		split(x, L - 1, x, y);
//		printf("[L:%d, R:%d]:\n", L, R);
//		print(y);
		rt = merge(x, z);
//		fa[rt] = 0;  // 将新根的父亲设为 0 
	}
	
	// 已知节点编号, 求排名 
	int getrnk(int p) {
		int res = siz[ls[p]] + len(p);
		while (p != rt && p) {
//			puts("Die in getrnk.");
//			printf("p:%d\n", rt);
			if (p != ls[fa[p]]) res += siz[ls[fa[p]]] + len(fa[p]);
			p = fa[p];
		}
		return res;
	}
	
	// 已知排名, 求真实编号 
	int getid(int p, int k) {
//		puts("Die in getid.");
//		printf("p:%d, k:%d\n", p, k);
//		system("pause");
		if (!p) return 1;
		if (siz[ls[p]] >= k) return getid(ls[p], k);
		k -= siz[ls[p]];
		if (k <= len(p)) return l[p] + k - 1;
		return getid(rs[p], k - len(p));
	}
} ftp;

int main() {
//	freopen("3.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	srand(time(0));
	scanf("%d%d", &n, &m);
	ftp.insert(1, 1, n), ftp.fa[0] = 0;
	
//	printf("rt:%d\n", ftp.rt);
//	ftp.print(ftp.rt);
//	printf("mp[1]:%d\n", mp[1]);
	int ans = 0;
	while (m--) {
//		puts("|||||||||||||||||||||||||||||||||||");
		int op, x, y;
		scanf("%d%d", &op, &x);
		x -= ans;
		if (op == 4) {
			printf("%d\n", (ans = ftp.getid(ftp.rt, x)));
			continue;
		}
		
		if (op == 1) scanf("%d", &y), y -= ans;
//		printf("x:%d, y:%d\n", x, (op == 1 ? y : -1));
		map<int, int>::iterator it = --mp.upper_bound(x);
		int l = it -> first, p = it -> second, r = ftp.r[p];
		
//		printf("p:%d, l:%d, r:%d\n", p, l, r);
		
//		system("pause");
		printf("%d\n", (ans = ftp.getrnk(p) - (r - x)));
		
		ftp.erase(ans - (x - l), ans + (r - x));
//		puts("==============================");
//		puts("After erase:");
//		ftp.print(ftp.rt);
		if (x > l) ftp.insert(ans - (x - l), l, x - 1);
		if (x < r) ftp.insert(ans, x + 1, r);
//		puts("==============================");
//		puts("After first insert:");
//		ftp.print(ftp.rt);
		 
		if (op == 1) ftp.insert(ans, y, y);  // 在原来排名的位置加上 
		if (op == 2) ftp.insert(1, x, x);
		if (op == 3) ftp.insert(n, x, x);
//		puts("==============================");
//		puts("After second insert:");
//		ftp.print(ftp.rt);
	}
	return 0;
}