方伯伯正在做他的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的用户编号，执行完该操作后需要输出当前操作用户的编号。
但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：
1 x+a y+a
2 x+a
3 x+a
4 k+a
其中a为上一次操作得到的输出，一开始a=0。
例如：上一次操作得到的输出是5这一次操作的输入为：1 13 15因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10现在你截获了方伯伯的所有操作，希望你能给出结果。
这些操作看起来就像是用平衡树来写，记录每个编号在平衡树中的节点（记录在一个map里），然后每次跳平衡树的父亲就可以得到它的排名。
这里用fhq-treap来实现，但是我们发现这个用户太多了，要动态开点。
这里简单介绍一下动态开点的平衡树。每个节点不再代表一个点，而是代表一段编号连续的区间，每个节点自己的大小也就成了区间的长度。
struct fhq_treap{
int sz, l, r, len, key, son[2], fa;
}tr[N];
这样的话pushup也要改变。
void push_up(int x) {
tr[x].sz = tr[x].len;/*重点*/
if (tr[x].son[0]) tr[tr[x].son[0]].fa = x, tr[x].sz += tr[tr[x].son[0]].sz;
if (tr[x].son[1]) tr[tr[x].son[1]].fa = x, tr[x].sz += tr[tr[x].son[1]].sz;
}
merge其实是一样的，关键是split操作现在的意义，如果是按size split的话，代表将前k个数（不是节点）中最后一个完整的节点和其它分离开。为了实现这样的功能还需改变写法，变成下面这样。
void split(int p, int k, int &x, int &y) {
if (!p) x = y = 0;
else {
if (tr[tr[p].son[0]].sz + tr[p].len <= k) {
x = p;
split(tr[p].son[1], k - tr[tr[p].son[0]].sz - tr[p].len, tr[x].son[1], y);
} else {
y = p;
split(tr[p].son[0], k, x, tr[y].son[0]);
}
push_up(p);
}
}
我们为了查找排名为 \(k\) 的用户坐在区间我们还需实现这样一个函数，改函数返回的是排名为 \(k\) 的用户所在的节点：
int Kth(int p, int k) {
if (tr[tr[p].son[0]].sz >= k) return Kth(tr[p].son[0], k);
else {
k -= tr[tr[p].son[0]].sz;
if (k <= tr[p].len) return p;
return Kth(tr[p].son[1], k - tr[p].len);
}
}
动态开点平衡树的具体操作就是如果我们需要搞一个用户，我们先找到它所在的节点，这个节点可能代表一段连续编号的区间，并且一定包含改用户，然后把这个节点分裂成三个节点（可以新建三个节点也可以垃圾回收），再merge会平衡树里。可以发现这样做的空间复杂度是 \(O(m)\) 的。
可是这道题还比较毒瘤的一点是它只告诉你用户编号，这时我们需要一个映射把用户编号映射到平衡树上的节点，而我们又不可能一对一的映射，因为这在分裂节点时的时间复杂度是不对的。有一个trick是只记录每个节点右端点所在节点，然后再map中二分找，找到第一个大于等于当前询问编号的肯定就是和当前询问编号在同一节点的。
具体来看main函数怎么写：
int main() {
srand(19260817);
read(n); read(m);
root = new_node(1, n);
pos[n] = root;
while (m--) {
ll t, x, y;
int a, b, c;
read(t); read(x);
x -= ans;
if (t == 1) {
read(y);
y -= ans;
map<ll, ll>::iterator node = pos.lower_bound(x);
int Node = node->second;
int Rank = Find_Rank(Node);
ans = Rank - (tr[Node].r - x);
split(root, Rank - tr[Node].len, a, c);
tr[a].fa = tr[c].fa = 0;
split(c, tr[Node].len, b, c);
tr[b].fa = tr[c].fa = 0;
root = a;
pos.erase(node->first);
int l = tr[Node].l, r = tr[Node].r;
if (l < x) root = merge(root, pos[x - 1] = new_node(l, x - 1));
init(b, y, y);
root = merge(root, pos[y] = b);
if (r > x) root = merge(root, pos[r] = new_node(x + 1, r));
root = merge(root, c);
} else if (t == 2) {
map<ll, ll>::iterator node = pos.lower_bound(x);
int Node = node->second;
int Rank = Find_Rank(Node);
ans = Rank - (tr[Node].r - x);
split(root, Rank - tr[Node].len, a, c);
tr[a].fa = tr[c].fa = 0;
split(c, tr[Node].len, b, c);
tr[b].fa = tr[c].fa = 0;
root = a;
pos.erase(node->first);
int l = tr[Node].l, r = tr[Node].r;
init(b, x, x);
root = merge(pos[x] = b, root);
if (l < x) root = merge(root, pos[x - 1] = new_node(l, x - 1));
if (r > x) root = merge(root, pos[r] = new_node(x + 1, r));
root = merge(root, c);
} else if (t == 3) {
map<ll, ll>::iterator node = pos.lower_bound(x);
int Node = node->second;
int Rank = Find_Rank(Node);
ans = Rank - (tr[Node].r - x);
split(root, Rank - tr[Node].len, a, c);
tr[a].fa = tr[c].fa = 0;
split(c, tr[Node].len, b, c);
tr[b].fa = tr[c].fa = 0;
root = a;
pos.erase(node->first);
int l = tr[Node].l, r = tr[Node].r;
if (l < x) root = merge(root, pos[x - 1] = new_node(l, x - 1));
if (r > x) root = merge(root, pos[r] = new_node(x + 1, r));
root = merge(root, c);
init(b, x, x);
root = merge(root, pos[x] = b);
} else {
int Node = Kth(root, x);
split(root, x - 1, a, b);
tr[a].fa = tr[b].fa = 0;
x -= tr[a].sz;
ans = tr[Node].l + x - 1;
root = merge(a, b);
}
printf("%d\n", ans);
}
return 0;
}
看完之后是不是非常没有写的欲望，反正我是没有，但其实这个代码的思路还是非常顺的，懂了思路这么一路写下来也就很快了（另外操作23基本相同，操作4不需要分裂区间，也就是说其实只需要实现两个比较难的部分，还是非常友好的）。
原文：https://www.cnblogs.com/zcr-blog/p/13742445.html