洛谷 P6136 题解
首先，推销一下我的新博客：https://yce3216037.github.io/post/luo-gu-p6136-ti-jie
这道题目怎么能没有AVL树呢？其实，在P3369，我就写了一篇AVL树的题解，链接在这里（第二篇可能没有图片，见谅），我就不再赘述了：
https://www.luogu.com.cn/blog/YCE-22/solution-p3369
https://yce3216037.github.io/post/luo-gu-p3369-ti-jie
唯一需要注意的是，要找排名的数不一定有，所以还需要增加一个查找函数，代码如下：
inline AVLtree Find(AVLtree& p, int x) {
if (!p) return NULL;//找不到就返回空，否则就返回地址
if (p->data == x) return p;
if (p->data > x) return Find(p->ls, x);
return Find(p->rs, x);
}
inline AVLtree find(int x) {
return Find(root, x);
}
如果找不到这个数，就将这个数改为它的后继，所以，还需要预先加一个极大值来保证能过找到这个排名。
代码如下：
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
FILE *fin, *fout;
inline int read(int &x) {//快读，这题常数优化很重要
char c = 0; int f = x = 0;
while (c < 48 || c > 57) {
if (c == -1) return 0;
if (c == '-') f = 1; c = fgetc(fin);
}
while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
if (f) x = -x; return 1;
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
return read(x) + read(args...);
}
inline int write(int x) {
if (x < 0) return fputc(45, fout), write(-x);
if (x > 9) write(x / 10);
return fputc((x % 10) | 48, fout), 1;
}
struct AVLnode;
typedef AVLnode* AVLtree;
struct AVLnode {//这个部分在之前P3369中的题解已经详细讲述了，这里我就不写注释了。
int data, high;
int freq, size;
AVLtree ls, rs;
AVLnode(): data(0), high(1), freq(1), size(1), ls(NULL), rs(NULL){}
AVLnode(int a): data(a), high(1), freq(1), size(1), ls(NULL), rs(NULL){}
};
inline int GetSize(AVLtree p) {
if (p == NULL) return 0;
return p->size;
}
inline int GetHigh(AVLtree p) {
if (p == NULL) return 0;
return p->high;
}
struct AVL {
AVLtree root;
inline void update(AVLtree& p) {
p->size = GetSize(p->ls) + GetSize(p->rs) + p->freq;
p->high = max(GetHigh(p->ls), GetHigh(p->rs)) + 1;
}
inline void LeftPlus(AVLtree& p) {
AVLtree q;
q = p->ls;
p->ls = q->rs;
q->rs = p;
update(p);
update(q);
p = q;
}
inline void RightPlus(AVLtree& p) {
AVLtree q;
q = p->rs;
p->rs = q->ls;
q->ls = p;
update(p);
update(q);
p = q;
}
inline void LeftRight(AVLtree& p) {
RightPlus(p->ls);
LeftPlus(p);
}
inline void RightLeft(AVLtree& p) {
LeftPlus(p->rs);
RightPlus(p);
}
inline void Insert(AVLtree &p, int x) {
if (p == NULL) {
p = new AVLnode(x);
return;
}
if (p->data == x) {
++(p->freq);
update(p);
return;
}
if (p->data > x) {
Insert(p->ls, x), update(p);
if (GetHigh(p->ls) - GetHigh(p->rs) == 2) {
if (x < p->ls->data)
LeftPlus(p);
else
LeftRight(p);
}
}
else {
Insert(p->rs, x), update(p);
if (GetHigh(p->rs) - GetHigh(p->ls) == 2) {
if (x > p->rs->data)
RightPlus(p);
else
RightLeft(p);
}
}
update(p);
}
inline void insert(int x) {
Insert(root, x);
}
inline AVLtree Find(AVLtree& p, int x) {//只不过多了一个查找操作
if (!p) return NULL;
if (p->data == x) return p;
if (p->data > x) return Find(p->ls, x);
return Find(p->rs, x);
}
inline AVLtree find(int x) {
return Find(root, x);
}
inline void Erase(AVLtree& p, int x) {
if (p == NULL) return;
if (p->data > x) {
Erase(p->ls, x), update(p);
if (GetHigh(p->rs) - GetHigh(p->ls) == 2) {
if (GetHigh(p->rs->rs) >= GetHigh(p->rs->ls))
RightPlus(p);
else
RightLeft(p);
}
}
else if(p->data < x) {
Erase(p->rs, x), update(p);
if (GetHigh(p->ls) - GetHigh(p->rs) == 2) {
if (GetHigh(p->ls->ls) >= GetHigh(p->ls->rs))
LeftPlus(p);
else
LeftRight(p);
}
}
else {
if (p->freq > 1) {
--(p->freq);
update(p);
return;
}
if (p->ls && p->rs) {
AVLtree q = p->rs;
while (q->ls) q = q->ls;
p->freq = q->freq;
p->data = q->data, q->freq = 1;
Erase(p->rs, q->data);
update(p);
if (GetHigh(p->ls) - GetHigh(p->rs) == 2) {
if (GetHigh(p->ls->ls) >= GetHigh(p->ls->rs))
LeftPlus(p);
else
LeftRight(p);
}
}
else {
AVLtree q = p;
if (p->ls) p = p->ls;
else if (p->rs) p = p->rs;
else p = NULL;
delete q;
q = NULL;
}
}
if (p == NULL) return;
update(p);
}
inline void erase(int x) {
Erase(root, x);
}
inline int get_val(AVLtree p, int rank) {
if (GetSize(p->ls) >= rank) return get_val(p->ls, rank);
if (GetSize(p->ls) + p->freq >= rank) return p->data;
return get_val(p->rs, rank - GetSize(p->ls) - p->freq);
}
inline int GetVal(int rank) {
return get_val(root, rank);
}
inline int get_rank(AVLtree p, int val) {
if (p->data == val) return GetSize(p->ls) + 1;
if (p->data > val) return get_rank(p->ls, val);
return get_rank(p->rs, val) + GetSize(p->ls) + p->freq;
}
inline int GetRank(int val) {
return get_rank(root, val);
}
inline int GetPrev(int val) {
AVLtree ans = new AVLnode(-1LL << 42), p = root;
while (p) {
if (p->data == val) {
if (p->ls) {
p = p->ls;
while (p->rs)
p = p->rs;
ans = p;
}
break;
}
if (p->data < val && p->data > ans->data) ans = p;
p = p->data < val ? p->rs : p->ls;
}
return ans->data;
}
inline int GetNext(int val) {
AVLtree ans = new AVLnode(1LL << 42), p = root;
while (p) {
if (p->data == val) {
if (p->rs) {
p = p->rs;
while (p->ls)
p = p->ls;
ans = p;
}
break;
}
if (p->data > val && p->data < ans->data) ans = p;
p = p->data < val ? p->rs : p->ls;
}
return ans->data;
}
};
AVL a;
int n, m, x, opt, last, ans;
signed main() {
#ifdef ONLINE_JUDGE
fin = stdin;
fout = stdout;
#else
fin = fopen("P6136.in", "rb");
fout = fopen("P6136.out", "wb");
#endif
read(n, m), a.insert(1LL << 42);//极大值先插入
for (int i = 1; i <= n; ++i) read(x), a.insert(x);//边读入边插入
for (int i = 1; i <= m; ++i) {
read(opt, x), x ^= last;//输入经过加密，要先解密
switch(opt) {
case 1: a.insert(x); break;
case 2: a.erase(x); break;
case 3:
if (!a.find(x)) x = a.GetNext(x);//如果找不到，就改为后继
last = a.GetRank(x), ans ^= last; break;
case 4: last = a.GetVal(x), ans ^= last; break;
case 5: last = a.GetPrev(x), ans ^= last; break;
case 6: last = a.GetNext(x), ans ^= last; break;
}
}
write(ans);
return 0;
}