难度：NOI/NOI+/CTSC

题目描述

        方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户，编号为1～n“，一开始他们按照编号排名。
        方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：

  • 操作格式为1 x y，意味着将编号为x的用户编号改为y，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证x必然出现在队列中，同时，1是一个当前不在排名中的编号。
  • 操作格式为2 x，意味着将编号为x的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为x用户的排名。
  • 操作格式为3 x，意味着将编号为x的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为x用户的排名。
  • 操作格式为4 k，意味着查询当前排名为k的用户编号，执行完该操作后需要输出当前操作用户的编号。

        但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：

  • x+a y+a
  • x+a
  • x+a
  • k+a

        其中a为上一次操作得到的输出，一开始a=0。
        例如：上一次操作得到的输出是5这一次操作的输入为：1 13 15因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10现在你截获了方伯伯的所有操作，希望你能给出结果。

输入格式

        输入的第1行包含2个用空格分隔的整数n和m，表示初始用户数和操作数。此后有m行，每行是一个询问，询问格式如上所示。对于 100% 的数据，$1\leq n\leq 10^8，1\leq m\leq 10^5$

输出格式

        输出包含m行。每行包含一个整数，其中第i行的整数表示第i个操作的输出。

输入输出样例

Sample input

10 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9

Sample ouput

2
2
2
4
3
5
5
7
8
11

题解

        比较狠的数据结构题。首先拿平衡树维护这应该都能看出来，但是发现n的范围是那样大，不可能为每一个都开一个新结点，于是这里的思路就是缩点：将一段区间内的所有点看成一个点，等到需要时再将点分拆，这是本题基本的思想。
        用缩点后的平衡数可以解决一部分操作，但是本题中很坑的一点是它还需要编号修改。我们建立的平衡树是按照排名进行组织的，已经失去了维护编号的能力，没法再索引编号。这里当然可以再建一棵平衡树，不过两棵平衡树都需要缩点再分拆，还需要交互，需要很好的码力。
        这里一个简便的操作是用动态开点的线段树维护用户编号对应的结点编号（其实本质上还是平衡树），容易和平衡树交互来完成这四种操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>

#define N 100005
using namespace std;
struct Node {
    int l, r, num, k, fa;
    int L, R;
} nd[N << 7];
struct STNode {
    int l, r, v;
} stnd[N << 7];
int n, m, last, root, stroot;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline int newNode(int l, int r) {
    static int cnt = 1;
    nd[cnt].L = l, nd[cnt].R = r, nd[cnt].num = r - l + 1, nd[cnt].k = rand();
    return cnt++;
}

inline void update(int x) {
    nd[x].num = nd[nd[x].l].num + nd[nd[x].r].num + nd[x].R - nd[x].L + 1;
    nd[nd[x].l].fa = nd[nd[x].r].fa = x;
}

inline int getNode(int s) {
    static int ct = 1;
    stnd[ct].v = stnd[s].v;
    return ct++;
}

void ins(int rt, int l, int r, int k, int L = 1, int R = static_cast<int>(2e8)) {//线段树修改
    if (L >= l && R <= r) {
        stnd[rt].v = k;
        return;
    }
    int mid = (L + R) >> 1;
    if (l > mid) {
        if (stnd[rt].r == 0)stnd[rt].r = getNode(rt);
        ins(stnd[rt].r, l, r, k, mid + 1, R);
    } else if (r <= mid) {
        if (stnd[rt].l == 0)stnd[rt].l = getNode(rt);
        ins(stnd[rt].l, l, r, k, L, mid);
    } else {
        if (stnd[rt].r == 0)stnd[rt].r = getNode(rt);
        if (stnd[rt].l == 0)stnd[rt].l = getNode(rt);
        ins(stnd[rt].l, l, mid, k, L, mid), ins(stnd[rt].r, mid + 1, r, k, mid + 1, R);
    }
}

int get(int rt, int k, int L = 1, int R = static_cast<int>(2e8)) {//线段树查询
    int mid = (L + R) >> 1;
    if (k <= mid) {
        if (stnd[rt].l == 0)return stnd[rt].v;
        return get(stnd[rt].l, k, L, mid);
    } else {
        if (stnd[rt].r == 0)return stnd[rt].v;
        return get(stnd[rt].r, k, mid + 1, R);
    }
}

inline int getRK(int x, int obj) {//获取排名
    int to = x, ans = 0, i = 0;
    while (to) {
        if (i == 0)ans += nd[nd[to].l].num + (nd[to].R >= obj && nd[to].L <= obj ? obj : nd[to].R) - nd[to].L + 1;
        i = nd[nd[to].fa].l == to, to = nd[to].fa;
    }
    return ans;
}

int fd(int rt, int s) {//查找结点
    if (nd[nd[rt].l].num + nd[rt].R - nd[rt].L + 1 < s)
        return fd(nd[rt].r, s - nd[nd[rt].l].num - nd[rt].R + nd[rt].L - 1);
    else if (s <= nd[nd[rt].l].num)return fd(nd[rt].l, s);
    return nd[rt].L + s - nd[nd[rt].l].num - 1;
}

void split(int rt, int &a, int &b, int s) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (nd[nd[rt].l].num + nd[rt].R - nd[rt].L + 1 <= s)
        a = rt, split(nd[rt].r, nd[a].r, b, s - nd[nd[rt].l].num - nd[rt].R + nd[rt].L - 1);
    else b = rt, split(nd[rt].l, a, nd[b].l, s);
    update(rt);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (nd[a].k < nd[b].k)rt = b, merge(nd[rt].l, a, nd[b].l);
    else rt = a, merge(nd[rt].r, nd[a].r, b);
    update(rt);
}

inline int change(int s, int x) {//结点分拆
    if (nd[s].L == x && nd[s].R == x)return s;
    int pk = getRK(s, nd[s].R), a, b, c, r, p, ans;
    split(root, a, c, pk), split(a, a, b, pk - (nd[s].R - nd[s].L + 1)), r = nd[b].R;
    if (nd[b].L == x) {
        p = newNode(x, x), ins(stroot, x, x, p), nd[b].num--, nd[b].L = x + 1, merge(b, p, b);
        merge(a, a, b), merge(root, a, c);
        return p;
    } else nd[b].R = x - 1, nd[b].num -= r - x + 1;
    ans = p = newNode(x, x), ins(stroot, x, x, p), merge(b, b, p);
    if (x < r)p = newNode(x + 1, r), ins(stroot, x + 1, r, p), merge(b, b, p);
    merge(a, a, b), merge(root, a, c);
    return ans;
}

int main() {
    srand(time(0));
    n = read(), m = read(), merge(root, root, newNode(1, n)), stroot = getNode(0), ins(stroot, 1, n, root);
    while (m--) {
        int opt = read(), x, y, p, a, b, c, d;
        if (opt == 1) {
            x = read(), y = read(), x -= last, y -= last, p = get(stroot, x), printf("%d\n", last = getRK(p, x));
            p = change(p, x), nd[p].L = nd[p].R = y, ins(stroot, y, y, p);
        } else if (opt == 2 || opt == 3) {
            x = read(), x -= last, p = get(stroot, x);
            p = change(p, x), printf("%d\n", last = d = getRK(p, nd[p].R));
            split(root, a, c, d), split(a, a, b, d - (nd[p].R - nd[p].L + 1));
            if (opt == 2)merge(b, b, a), merge(root, b, c);
            else merge(a, a, c), merge(root, a, b);
        } else x = read() - last, printf("%d\n", last = fd(root, x));
    }
    return 0;
}