Leo11 @ 2024-08-16 09:44:44
```cpp
/*
Tree<int, Greater<int> >tree; 从大到小
Tree<int, Less<int> >tree; 从小到大
tree.insert(x) 插入 x
tree.erase(x) 删除 x
tree.clear() 清空平衡树
tree.lower_bound(x) 第一个大于等于 x 的数
tree.upper_bound(x) 第一个大于 x 的数
tree.query(x) 查询 x 的排名
tree.find(x) 查询排名为 x 的数
tree.pre(x) 查询 x 的前驱（第一个小于 x 的数），等价于 tree.find(tree.query(tree.lower_bound(x)) - 1)
tree.size() 查询平衡树大小
tree.empty() 查询平衡树是否为空
*/
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void write(int n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
if(n > 9)
{
write(n / 10);
}
putchar(char(n % 10 + '0'));
}
template<typename t>
struct Less
{
bool operator()(register const t &a, register const t &b)
{
return a < b;
}
};
template<typename t>
struct Greater
{
bool operator()(const t &a, register const t &b)
{
return b < a;
}
};
template<typename t, typename Comper = Less<t> >
struct Tree
{
private:
struct node
{
node *ls, *rs;
int p, size;
t k;
}*root, *null;
mt19937 Rand;
Comper cmp;
inline void Clear(register node *&x)
{
if(x == null)
{
return;
}
Clear(x -> ls);
Clear(x -> rs);
delete x;
}
inline node* newnode(register const t &K)
{
node *p(new node);
return p -> ls = p -> rs = null, p -> k = K, p -> p = Rand(), p -> size = 1, p;
}
inline void update(register node *u)
{
u -> size = u -> ls -> size + u -> rs -> size + 1;
}
inline void split(register node *u, register const t &x, register node *&L, register node *&R)
{
if(u == null)
{
L = R = null;
return;
}
if(!cmp(x, u -> k))
{
L = u;
split(L -> rs, x, L -> rs, R);
update(L);
}
else
{
R = u;
split(R -> ls, x, L, R -> ls);
update(R);
}
}
inline node* merge(register node *L, register node *R)
{
if(L == null)
{
return R;
}
if(R == null)
{
return L;
}
if(L -> p > R -> p)
{
return L -> rs = merge(L -> rs, R), update(L), L;
}
else
{
return R -> ls = merge(L, R -> ls), update(R), R;
}
}
inline void Erase(register node *&x, register const t &K)
{
if(x == null)
{
return;
}
--x -> size;
if(x -> k == K)
{
node *temp(x);
x = merge(x -> ls, x -> rs);
delete temp;
return;
}
if(cmp(K, x -> k))
{
Erase(x -> ls, K);
}
else Erase(x -> rs, K);
}
inline int Rank(node *x, register const t &K)
{
if(x == null)
{
return 1;
}
if(cmp(x -> k, K))
{
return Rank(x -> rs, K) + x -> ls -> size + 1;
}
return Rank(x -> ls, K);
}
inline t kth(register node* now, register int x)
{
for(;;)
{
if(x <= now -> ls -> size)
{
now = now -> ls;
}
else if(x == now -> ls -> size + 1)
{
return now -> k;
}
else
{
x -= now -> ls -> size + 1;
now = now -> rs;
}
}
}
inline t lower__bound(register node *x, register const t &K)
{
if(x == null)
{
return t();
}
if(cmp(x -> k, K))
{
return lower__bound(x -> rs, K);
}
register t now(lower__bound(x -> ls, K));
if(now == t())
{
return x -> k;
}
return now;
}
inline t upper__bound(register node *x, register const t &K)
{
if(x == null)
{
return t();
}
if(!(cmp(K, x -> k)))
{
return upper__bound(x -> rs, K);
}
register t now(upper__bound(x -> ls, K));
if(now == t())
{
return x -> k;
}
return now;
}
inline t Pre(register node *x, register const t &K)
{
if(x == null)
{
return t();
}
if(!cmp(x -> k, K))
{
return Pre(x -> ls, K);
}
register t now(Pre(x -> rs, K));
if(now == t())
{
return x -> k;
}
return now;
}
public:
Tree()
{
Rand.seed((unsigned)time(0));
root = null = new node;
null -> ls = null -> rs = NULL;
null -> k = t();
null -> p = null -> size = 0;
}
~Tree()
{
Clear(root);
}
inline void clear()
{
Clear(root);
root = null;
}
inline void insert(register const t &K)
{
node *L, *R;
split(root, K, L, R);
root = merge(merge(L, newnode(K)), R);
}
inline void erase(register const t &K)
{
Erase(root, K);
}
inline int query(register const t &K)
{
return Rank(root, K);
}
inline t find(register const int &r)
{
return kth(root, r);
}
inline t lower_bound(register const t &K)
{
return lower__bound(root, K);
}
inline t upper_bound(register const t &K)
{
return upper__bound(root, K);
}
inline t pre(register const t &K)
{
return Pre(root, K);
}
inline int size()
{
return root -> size;
}
inline bool empty()
{
return root == null;
}
};
Tree<int, Less<int> > tree;
int n, m, last = 0, ans = 0;
map<int, int>mp;
signed main()
{
/*ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);*/
n = read(), m = read();
for(int i = 1; i <= n; i++)
{
tree.insert(read());
}
while(m--)
{
int op, x;
op = read(), x = read();
//cout << x << "\n";
x ^= last;
if(op == 1)
{
mp[x]++;
tree.insert(x);
}
else if(op == 2)
{
mp[x]--;
tree.erase(x);
}
else if(op == 3)
{
if(mp[x])
{
//cout << tree.query(x) << "\n";
last = tree.query(x);
ans ^= last;
}
else
{
tree.insert(x);
//cout << tree.query(x) << "\n";
last = tree.query(x);
ans ^= last;
tree.erase(x);
}
}
else if(op == 4)
{
last = tree.find(x);
ans ^= last;
//cout << tree.find(x) << "\n";
}
else if(op == 5)
{
if(mp[x])
{
//cout << tree.find(tree.query(tree.lower_bound(x)) - 1) << "\n";
//cout << tree.pre(x);
last = tree.pre(x);
ans ^= last;
}
else
{
tree.insert(x);
//cout << tree.find(tree.query(tree.lower_bound(x)) - 1) << "\n";
//cout << tree.pre(x) << "\n";
last = tree.pre(x);
ans ^= last;
tree.erase(x);
}
}
else if(op == 6)
{
if(mp[x])
{
last = tree.upper_bound(x);
ans ^= last;
//cout << tree.upper_bound(x) << "\n";
}
else
{
tree.insert(x);
last = tree.upper_bound(x);
ans ^= last;
//cout << tree.upper_bound(x) << "\n";
tree.erase(x);
}
}
}
write(ans);
}
```