已经不记得平衡树的样子了。
Statement
给定一个 \(1\sim n\) 的序列，你有如下几个操作：
- 改变一个人的编号
- 将一个人放在序列开头
- 将一个人放在序列结尾
- 查询排名为 \(k\) 的编号
对于每次操作，输出操作前这个人的排名。
Analysis
可以把操作看作是以下几个步骤
- 查找一个编号的排名
- 删除一个编号
- 在某一个位置加入一个编号
- 查询某个排名的编号
这非常的平衡树，但是人数是 \(10^8\) 级别，而操作次数缺不多，因此我们尝试用编号的区间表示平衡树上的节点，用一个 map 存下一个区间对应的平衡树上的节点即可。
这就是本题大部分的转化，代码实现比较重要。
const int N = 5e5 + 5;
map<int, int> rnk;
struct Treap {
int siz[N], ch[N][2], rnd[N], tot, L[N], R[N], fa[N], rt;
il int NewNode(int l, int r) {
siz[++tot] = r - l + 1;
L[tot] = l, R[tot] = r;
ch[tot][0] = ch[tot][1] = fa[tot] = 0; rnd[tot] = rand();
rnk[l] = tot; return tot;
}
il void pushup(int p) {
fa[ch[p][0]] = fa[ch[p][1]] = p;
siz[p] = (R[p] - L[p] + 1) // 当前节点 siz
+ siz[ch[p][0]] + siz[ch[p][1]];
}
il int merge(int x, int y) {
if (!x || !y) return x | y;
if (rnd[x] < rnd[y]) {
ch[x][1] = merge(ch[x][1], y);
pushup(x); return x;
}
else {
ch[y][0] = merge(x, ch[y][0]);
pushup(y); return y;
}
}
il void split(int p, int& x, int& y, int val) {
if (!p) return x = y = 0, void();
if (val <= siz[ch[p][0]]) {
split(ch[p][0], x, y, val);
ch[p][0] = y; y = fa[y] = p;
}
else {
split(ch[p][1], x, y, val - siz[ch[p][0]] - R[p] + L[p] - 1);
ch[p][1] = x; x = fa[x] = p;
}
pushup(p);
}
il int Rnk(int p) {
int ret = siz[p] - siz[ch[p][1]];
while (p != rt) {
if (ch[fa[p]][1] == p) ret += siz[fa[p]] - siz[ch[fa[p]][1]];
p = fa[p];
}
return ret;
}
il int kth(int p, int val) {
if (val <= siz[ch[p][0]]) return kth(ch[p][0], val);
val -= siz[ch[p][0]];
if (val - R[p] + L[p] - 1 <= 0) return L[p] + val - 1;
return kth(ch[p][1], val - R[p] + L[p] - 1);
}
il void ins(int p, int l, int r) {
int x, y;
split(rt, x, y, p - 1);
rt = merge(merge(x, NewNode(l, r)), y);
}
il void del(int l, int r) {
int x, y, z;
split(rt, x, z, r);
split(x, x, y, l - 1);
rt = merge(x, z);
}
}fhq;
int n, m, las;
int main() {
srand(time(nullptr));
read(n), read(m);
rnk[1] = 1; fhq.ins(1, 1, n);
for (int i = 1; i <= m; ++i) {
int opt = read();
if(opt == 1) {
int x = read() - las, y = read() - las;
int l = (--rnk.lower_bound(x + 1)) -> first, r = fhq.R[rnk[l]];
write(las = fhq.Rnk(rnk[l]) - r + x);
fhq.del(las - x + l, las - x + r);
if (x > l) fhq.ins(las - x + l, l, x - 1);
fhq.ins(las, y, y);
if (r > x) fhq.ins(las + 1, x + 1, r);
}
else if (opt == 2) {
int x = read() - las;
int l = (--rnk.lower_bound(x + 1)) -> first, r = fhq.R[rnk[l]];
write(las = fhq.Rnk(rnk[l]) - r + x);
fhq.del(las - x + l, las - x + r);
if (x > l) fhq.ins(las - x + l, l, x - 1);
if (r > x) fhq.ins(las, x + 1, r);
fhq.ins(1, x, x);
}
else if (opt == 3) {
int x = read() - las;
int l = (--rnk.lower_bound(x + 1)) -> first, r = fhq.R[rnk[l]];
write(las = fhq.Rnk(rnk[l]) - r + x);
fhq.del(las - x + l, las - x + r);
if (x > l) fhq.ins(las - x + l, l, x - 1);
if (r > x) fhq.ins(las, x + 1, r);
fhq.ins(n, x, x);
}
else {
int x = read() - las;
write(las = fhq.kth(fhq.rt, x));
}
}
return 0;
}
变量名字可能和实际用途不符。