[SCOI2014]方伯伯的OJ 题解
![[SCOI2014]方伯伯的OJ 题解](https://ksmeow.moe/wp-content/uploads/2018/04/180403d.jpg "180403d")
题目地址：洛谷：【P3285】[SCOI2014]方伯伯的OJ – 洛谷、BZOJ：Problem 3595. — [Scoi2014]方伯伯的Oj
题目描述
方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户，编号为1～n“，一开始他们按照编号排名。
方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：
1．操作格式为1 x y，意味着将编号为x的用户编号改为y，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证x必然出现在队列中，同时，1是一个当前不在排名中的编号。
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现在你截获了方伯伯的所有操作，希望你能给出结果。
输入输出格式
输入格式：
输入的第1行包含2个用空格分隔的整数n和m，表示初始用户数和操作数。此后有m行，每行是一个询问，询问格式如上所示。
输出格式：
输出包含m行。每行包含一个整数，其中第i行的整数表示第i个操作的输出。
输入输出样例
输入样例#1：
10 10 1 2 11 3 13 2 5 3 7 2 8 2 10 2 11 3 14 2 18 4 9
输出样例#1：
2 2 2 4 3 5 5 7 8 11
说明
对于 100% 的数据，1 <= n <= 10^8，1 <= m <= 10^5
输入保证对于所有的操作 1，2，3，x 必然已经出现在队列中，同时对于所有操作 1，1 <= y <= 2 * 10^8，并且y 没有出现在队列中。
对于所有操作 4，保证 1 <= k <= n。
题解
处理编号与splay节点编号之间的对应关系，我们可以考虑使用map。
第一位和最后一位的处理方法类似[ZJOI2006]书架 题解 | KSkun’s Blog。
改编号的操作，只需要把原来的编号从map中删去再加入新的编号即可。
但是这个n的数据范围有点吓人呀，我们考虑用一个节点表示一段连续区间，等到用到这个区间中某个值的时候再把它割成[l, i-1]、[i, i]、[i+1, r]三段，这样的话每次操作前要先割区间，然后继续。map存的也不再是编号-splay节点的关系了，而是区间左端点-splay节点，这样我们每次找到小于等于要处理编号的节点即可。
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF
: *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 1000005, INF = 1e9;
std::map<int, int> spn;
struct Node {
int fa, ch[2], l, r, siz;
} tr[MAXN];
int rt, tot;
inline void update(int p) {
tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].r - tr[p].l + 1;
}
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void rotate(int p) {
bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
tr[fa].fa = p; tr[p].ch[!t] = fa;
update(fa);
if(!tr[p].fa) rt = p;
}
inline void splay(int p, int tar) {
for(int fa = tr[p].fa; fa != tar; rotate(p), fa = tr[p].fa) {
if(tr[fa].fa != tar) rotate(isleft(p) == isleft(fa) ? fa : p);
}
update(p);
}
inline int queryn(int p, int rk) {
if(rk <= tr[tr[p].ch[0]].siz) {
return queryn(tr[p].ch[0], rk);
}
rk -= tr[tr[p].ch[0]].siz;
if(rk <= tr[p].r - tr[p].l + 1) {
splay(p, 0);
return tr[p].l + rk - 1;
}
rk -= tr[p].r - tr[p].l + 1;
return queryn(tr[p].ch[1], rk);
}
inline int querypre() {
int p = tr[rt].ch[0];
while(tr[p].ch[1]) p = tr[p].ch[1];
return p;
}
inline int querynxt() {
int p = tr[rt].ch[1];
while(tr[p].ch[0]) p = tr[p].ch[0];
return p;
}
inline void split(int p, int id) {
if(tr[p].l < id) {
int q = ++tot;
tr[q].ch[0] = tr[p].ch[0];
tr[tr[q].ch[0]].fa = q;
tr[p].ch[0] = q;
tr[q].l = tr[p].l; tr[q].r = id - 1;
tr[q].fa = p;
update(q);
spn[tr[q].l] = q;
}
if(tr[p].r > id) {
int q = ++tot;
tr[q].ch[1] = tr[p].ch[1];
tr[tr[q].ch[1]].fa = q;
tr[p].ch[1] = q;
tr[q].l = id + 1; tr[q].r = tr[p].r;
tr[q].fa = p;
update(q);
spn[tr[q].l] = q;
}
tr[p].l = tr[p].r = id;
update(p);
spn[id] = p;
}
inline int top(int p) {
splay(p, 0);
int res = tr[tr[p].ch[0]].siz + 1;
if(!tr[p].ch[0]) return res;
if(!tr[p].ch[1]) {
std::swap(tr[p].ch[0], tr[p].ch[1]);
return res;
}
int q = querynxt();
split(q, tr[q].l);
splay(q, p);
tr[q].ch[0] = tr[p].ch[0];
tr[tr[q].ch[0]].fa = q;
tr[p].ch[0] = 0;
update(p); update(q);
return res;
}
inline int bottom(int p) {
splay(p, 0);
int res = tr[tr[p].ch[0]].siz + 1;
if(!tr[p].ch[1]) return res;
if(!tr[p].ch[0]) {
std::swap(tr[p].ch[0], tr[p].ch[1]);
return res;
}
int q = querypre();
split(q, tr[q].r);
splay(q, p);
tr[q].ch[1] = tr[p].ch[1];
tr[tr[q].ch[1]].fa = q;
tr[p].ch[1] = 0;
update(p); update(q);
return res;
}
int n, m, op, x, y, ans;
int main() {
n = readint(); m = readint();
tot = 1;
tr[1].l = 1; tr[1].r = n; update(1); spn[1] = 1; rt = 1;
while(m--) {
op = readint(); x = readint() - ans; if(op == 1) y = readint() - ans;
int p;
if(op != 4) {
std::map<int, int>::iterator it = --spn.upper_bound(x);
p = it->second;
split(p, x);
}
if(op == 1) {
splay(p, 0);
ans = tr[tr[p].ch[0]].siz + 1;
spn.erase(tr[p].l);
tr[p].l = tr[p].r = y; spn[y] = p;
} else if(op == 2) {
ans = top(p);
} else if(op == 3) {
ans = bottom(p);
} else {
ans = queryn(rt, x);
}
printf("%d\n", ans);
}
return 0;
}
