题目地址：洛谷：【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;
}