Description：

有 $n$ 个用户，编号为 $1\sim n$ ，初始时按照编号排名， $m$ 个操作：

$1$ 、修改用户编号，输出该用户在队列中的位置。

$2$ 、将编号为 $x$ 的用户的排名提升到第一位，输出执行前编号为 $x$ 用户的排名。

$3$ 、将编号为 $x$ 的用户的排名降到最后一位，输出执行前编号为 $x$ 用户的排名。

$4$ 、查询当前排名为 $k$ 的用户编号，执行完后需要输出当前操作用户的编号。

$1\leqslant n\leqslant 10^8,1\leqslant m\leqslant 10^5$

Solution：

观察一下题目的操作不难看出应该用一棵平衡树维护所有用户的排名，因为排名要支持在最前面插入，在最后插入和查询第 $k$ 大，对于编号，可以不用平衡树，只用一个 $map$ 来记录每个编号的人在平衡树中的位置，这样可以直接找到编号为 $x$ 的用户，由于 $n$ 太大，但 $m$ 不太大，所以要动态开点， $map$ 里存的也是这段区间在平衡树中的位置，然后就是一个平衡树基本操作，分裂的函数有两种写法，一是把想要的那个位置拿出来，他两边分别建两个节点，这样每次只会分裂出要用的，常数比较小，还可以每次把这个区间等分成两半，让右半边做右子树，这样代码好写，这题都能过。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + (c ^ 48);

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

struct seg

{

	int l,r;

	bool operator < (seg b)const{return r < b.r;}

};

map<seg,int> p;

struct node

{

	int c[2],fa;

	int l,r;

	int siz;

	node(){siz = 0;}

}t[MAXN * 15];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

inline int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

inline void maintain(int rt)

{

	t[rt].siz = t[rt].r - t[rt].l + 1;

	if(t[rt].c[0] != 0)t[rt].siz += t[t[rt].c[0]].siz;

	if(t[rt].c[1] != 0)t[rt].siz += t[t[rt].c[1]].siz;

	return;

}

inline void rotate(int x)

{

	register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);connect(x,z,fy);

	maintain(y);maintain(x);

	return;

}

inline void splay(int x)

{

	while(t[x].fa != 0)

	{

		register int y = t[x].fa;

		if(t[y].fa == 0){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	root = x;

	return;

}

inline void init()

{

	register int k = newnode();

	t[k].l = 1;t[k].r = n;

	t[k].siz = n;

	root = 1;

	p[(seg){1,n}] = k;

	return;

}

inline void split(int rt,int v)

{

	if(v != t[rt].l)

	{

		register int k = newnode();

		p.erase(p.find((seg){t[rt].l,t[rt].r}));

		t[k].l = t[rt].l;t[k].r = v - 1;t[rt].l = v;

		p[(seg){t[rt].l,t[rt].r}] = rt;p[(seg){t[k].l,t[k].r}] = k;

		connect(t[rt].c[0],k,0);connect(k,rt,0);

		maintain(k);

	}

	if(v != t[rt].r)

	{

		register int k = newnode();

		p.erase(p.find((seg){t[rt].l,t[rt].r}));

		t[k].l = v + 1;t[k].r = t[rt].r;t[rt].r = v;

		p[(seg){t[rt].l,t[rt].r}] = rt;p[(seg){t[k].l,t[k].r}] = k;

		connect(t[rt].c[1],k,1);connect(k,rt,1);

		maintain(k);

	}

	return;

}

inline int find_kth(int k)

{

	register int cur = root;

	while(true)

	{

		register int ls = 0;

		if(t[cur].c[0] != 0)ls = t[t[cur].c[0]].siz;

		if(k <= ls)cur = t[cur].c[0];

		else if(k > ls + t[cur].r - t[cur].l + 1)

		{

			k -= ls + t[cur].r - t[cur].l + 1;

			cur = t[cur].c[1];

		}

		else

		{

			k -= ls;

			split(cur,t[cur].l + k - 1);

			return cur;

		}

	}

}

inline int find_val(int rt,int k)

{

	split(rt,k);

	return rt;

}

inline int remove(int k)

{

	register int pos = find_val(p.lower_bound((seg){k,k}) -> second,k);

	splay(pos);

	if(t[pos].c[0] == 0){root = t[pos].c[1];t[t[pos].c[1]].fa = 0;}

	else if(t[pos].c[1] == 0){root = t[pos].c[0];t[t[pos].c[0]].fa = 0;}

	else

	{

		register int nrt = t[root].c[1];

		while(t[nrt].c[0] != 0)nrt = t[nrt].c[0];

		splay(nrt);

		connect(t[pos].c[0],nrt,0);

		maintain(nrt);

	}

	t[pos].c[1] = t[pos].c[0] = t[pos].fa = 0;

	return pos;

}

inline int addfirst(int k)

{

	splay(find_val(p.lower_bound((seg){k,k}) -> second,k));

	register int res = t[t[root].c[0]].siz + 1;

	register int pos = remove(k);

	register int cur = root;

	while(t[cur].c[0] != 0)cur = t[cur].c[0];

	splay(cur);

	connect(pos,cur,0);

	maintain(pos);maintain(cur);

	return res;

}

inline int addback(int k)

{

	splay(find_val(p.lower_bound((seg){k,k}) -> second,k));

	register int res = t[t[root].c[0]].siz + 1;

	register int pos = remove(k);

	register int cur = root;

	while(t[cur].c[1] != 0)cur = t[cur].c[1];

	splay(cur);

	connect(pos,cur,1);

	maintain(pos);maintain(cur);

	return res;

}

inline int change(int x,int y)

{

	register int pos = p.lower_bound((seg){x,x}) -> second;

	pos = find_val(pos,x);

	splay(pos);

	t[pos].l = t[pos].r = y;

	p.erase(p.find((seg){x,x}));

	p[(seg){y,y}] = pos;

	maintain(pos);

	return t[t[pos].c[0]].siz + 1;

}

void print(int k)

{

	if(k < 10){putchar(k + '0');return;}

	print(k / 10);

	putchar(k % 10 + '0');

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	init();

	register int opt,x,y;

	register int lastans = 0;

	for(register int i = 1;i <= m;++i)

	{

		opt = read();

		if(opt == 1)

		{

			x = read() - lastans;y = read() - lastans;

			print(lastans = change(x,y));puts("");

		}

		if(opt == 2)

		{

			x = read() - lastans;

			print(lastans = addfirst(x));puts("");

		}

		if(opt == 3)

		{

			x = read() - lastans;

			print(lastans = addback(x));puts("");

		}

		if(opt == 4)

		{

			x = read() - lastans;

			print(lastans = t[find_kth(x)].l);puts("");

		}

	}

	return 0;

}