方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户，编号为1～n“，一开始他们按照编号排名。
方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：
1．操作格式为1 x y，意味着将编号为x的用户编号改为y，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证x必然出现在队列中，同时，y是一个当前不在排名中的编号。
2．操作格式为2 x，意味着将编号为x的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为x用户的排名。
3．操作格式为3 x，意味着将编号为x的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为x用户的排名。
4．操作格式为4 k，意味着查询当前排名为k的用户编号，执行完该操作后需要输出当前操作用户的编号。
但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：
例如：上一次操作得到的输出是5这一次操作的输入为：1 13 15因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10现在你截获了方伯伯的所有操作，希望你能给出结果。
对于 100% 的数据，\(1 \leq n \leq 10^8,1 \leq m \leq 10^5\)
刚开始：这不俩平衡树就做完了吗。然后看到了数据范围
其实这个也不算是瓶颈，毕竟有用的点只有m同级个，所以我们考虑将没有用到的编号的区间缩成一个点，然后用平衡树维护，每次如果要用到这里的点就把它分裂出来，这样操作234都可以简单完成
1操作就更简单了，多开一个平衡树维护这个编号对应在另一个平衡树上的点，这个其实不需要平衡树，用map就可以了
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
const int N = 1e8;
const int M = 1e6;
using namespace std;
int n,m,a,node_cnt,rt;
map <int,int> f;
struct Splay
{
int ch[2],fa,size,L,R;
}t[M + 5];
int chk(int x)
{
return t[t[x].fa].ch[1] == x;
}
void pushup(int x)
{
t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + t[x].R - t[x].L + 1;
}
void rot(int x)
{
int y = t[x].fa,z = t[y].fa,k = chk(x);
if (z)
t[z].ch[chk(y)] = x;
t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1];
t[t[x].ch[k ^ 1]].fa = y;
t[x].ch[k ^ 1] = y;
t[y].fa = x;
pushup(y);
pushup(x);
}
void splay(int x,int goal = 0)
{
while (t[x].fa != goal)
{
int y = t[x].fa,z = t[y].fa;
if (z != goal)
{
if (chk(x) == chk(y))
rot(y);
else
rot(x);
}
rot(x);
}
if (!goal)
rt = x;
}
void del(int x)
{
int l = t[x].ch[0],r = t[x].ch[1];
while (t[l].ch[1])
l = t[l].ch[1];
while (t[r].ch[0])
r = t[r].ch[0];
if (!l && !r)
{
rt = 0;
return;
}
if (l && r)
{
splay(l);
splay(r,l);
t[r].ch[0] = t[x].fa = 0;
t[x].size = 1;
pushup(r);
pushup(l);
}
else
if (!r || !l)
{
splay(l + r,rt);
rt = l + r;
t[rt].fa = 0;
t[x].ch[0] = t[x].ch[1] = 0;
t[x].size = 1;
}
}
void split(int x,int mid)
{
int L = t[x].L,R = t[x].R;
if (L == R)
return;
if (L == mid)
{
int rc = ++node_cnt;
t[rc].ch[1] = t[x].ch[1];
t[t[x].ch[1]].fa = rc;
t[x].ch[1] = rc;
t[rc].fa = x;
t[x].R = L;
f[R] = rc;
f[L] = x;
t[rc].L = L + 1;
t[rc].R = R;
pushup(rc);
pushup(x);
}
else
if (R == mid)
{
int lc = ++node_cnt;
t[lc].ch[0] = t[x].ch[0];
t[t[x].ch[0]].fa = lc;
t[x].ch[0] = lc;
t[lc].fa = x;
f[R] = x;
f[R - 1] = lc;
t[x].L = R;
t[lc].R = R - 1;
t[lc].L = L;
pushup(lc);
pushup(x);
}
else
{
int lc = ++node_cnt,rc = ++node_cnt;
t[lc].ch[0] = t[x].ch[0];
t[rc].ch[1] = t[x].ch[1];
t[t[x].ch[0]].fa = lc;
t[t[x].ch[1]].fa = rc;
t[x].ch[0] = lc;
t[x].ch[1] = rc;
t[lc].fa = t[rc].fa = x;
f[mid - 1] = lc;
f[mid] = x;
f[R] = rc;
t[x].L = t[x].R = mid;
t[lc].L = L;
t[lc].R = mid - 1;
t[rc].L = mid + 1;
t[rc].R = R;
pushup(lc);
pushup(rc);
pushup(x);
}
splay(x);
}
void ins(int x,int f)
{
if (!rt)
{
rt = x;
return;
}
int u = rt;
while (t[u].ch[f])
t[u].size++,u = t[u].ch[f];
t[u].size++;
t[u].ch[f] = x;
t[x].fa = u;
splay(x);
}
int kths(int x)
{
splay(x);
return t[x].size - t[t[x].ch[1]].size;
}
int kth(int x)
{
int u = rt,sm;
while (1)
{
sm = t[t[u].ch[0]].size + t[u].R - t[u].L + 1;
if (x > sm)
x -= sm,u = t[u].ch[1];
else
if (x <= sm && x > t[t[u].ch[0]].size)
return t[u].L + x - 1 - t[t[u].ch[0]].size;
else
u = t[u].ch[0];
}
}
int main()
{
//freopen("3285.in","r",stdin);
//freopen("aa.out","w",stdout);
scanf("%d%d",&n,&m);
rt = node_cnt = 1;
t[1].L = 1;
t[1].R = n;
t[1].size = n;
f[n] = 1;
int opt,x,y;
while (m--)
{
scanf("%d%d",&opt,&x);
x -= a;
if (opt == 1)
{
scanf("%d",&y);
y -= a;
int id = f.lower_bound(x) -> second;
split(id,x);
a = kths(id);
t[id].L = t[id].R = y;
f[y] = id;
printf("%d\n",a);
}
else
if (opt == 2)
{
int id = f.lower_bound(x) -> second;
split(id,x);
a = kths(id);
printf("%d\n",a);
del(id);
ins(id,0);
}
else
if (opt == 3)
{
int id = f.lower_bound(x) -> second;
split(id,x);
a = kths(id);
printf("%d\n",a);
del(id);
ins(id,1);
}
else
if (opt == 4)
{
a = kth(x);
printf("%d\n",a);
}
}
return 0;
}
原文：https://www.cnblogs.com/sdlang/p/13124292.html