ZMQ_Ink6556 @ 2024-08-26 17:17:18
```cpp
#include<bits/stdc++.h>
using namespace std;
int rt , tot , fa[100005] , ch[100005][5] , val[100005] , cnt[100005] , sz[100005] , n , m , x , last , ans;
char op;
struct Splay
{
inline void maintain(const int &x)
{
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
return;
}
inline bool get(const int &x)
{
return x == ch[fa[x]][1];
}
inline void clear(const int &x)
{
ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
return;
}
inline void rotate(const int &x)
{
const int y = fa[x] , z = fa[y] , chk = get(x);
if(chk ^ 1)
{
ch[y][chk] = ch[x][1];
if(ch[x][1])
{
fa[ch[x][1]] = y;
}
ch[x][1] = y;
}
else
{
ch[y][chk] = ch[x][0];
if(ch[x][0])
{
fa[ch[x][0]] = y;
}
ch[x][0] = y;
}
fa[y] = x;
fa[x] = z;
if(z)
{
if(y == ch[z][1])
{
ch[z][1] = x;
}
else
{
ch[z][0] = x;
}
}
maintain(y);
maintain(x);
return;
}
inline void splay(const int &x)
{
for(register int f = fa[x] ; f = fa[x] , f ; rotate(x))
{
if(fa[f])
{
if(get(x) == get(f))
{
rotate(f);
}
else
{
rotate(x);
}
}
}
rt = x;
return;
}
inline void ins(const int &k)
{
if(!rt)
{
tot++;
val[tot] = k;
cnt[tot]++;
rt = tot;
maintain(rt);
return;
}
register int cur = rt , f = 0;
while(1)
{
if(val[cur] == k)
{
cnt[cur]++;
maintain(cur);
maintain(f);
splay(cur);
return;
}
f = cur;
if(val[cur] < k)
{
cur = ch[cur][1];
}
else
{
cur = ch[cur][0];
}
if(!cur)
{
tot++;
val[tot] = k;
cnt[tot]++;
fa[tot] = f;
if(val[f] < k)
{
ch[f][1] = tot;
}
else
{
ch[f][0] = tot;
}
maintain(tot);
maintain(f);
splay(tot);
return;
}
}
return;
}
inline int rk(const int &k)
{
register int res = 0 , cur = rt;
while(1)
{
if(k < val[cur])
{
cur = ch[cur][0];
}
else
{
res += sz[ch[cur][0]];
if(!cur)
{
return res + 1;
}
if(k == val[cur])
{
splay(cur);
return res + 1;
}
res += cnt[cur];
cur = ch[cur][1];
}
}
return 0;
}
inline int kth(register int k)
{
register int cur = rt;
while(1)
{
if(ch[cur][0] && k <= sz[ch[cur][0]])
{
cur = ch[cur][0];
}
else
{
k -= cnt[cur] + sz[ch[cur][0]];
if(k <= 0)
{
splay(cur);
return val[cur];
}
cur = ch[cur][1];
}
}
return 0;
}
inline int pre()
{
register int cur = ch[rt][0];
if(!cur)
{
return cur;
}
while(ch[cur][1])
{
cur = ch[cur][1];
}
splay(cur);
return cur;
}
inline int nxt()
{
register int cur = ch[rt][1];
if(!cur)
{
return cur;
}
while(ch[cur][0])
{
cur = ch[cur][0];
}
splay(cur);
return cur;
}
inline void del(const int k)
{
rk(k);
if(cnt[rt] > 1)
{
cnt[rt]--;
maintain(rt);
return;
}
if(!ch[rt][0] && !ch[rt][1])
{
clear(rt);
rt = 0;
return;
}
if(!ch[rt][0])
{
int cur = rt;
rt = ch[rt][1];
fa[rt] = 0;
clear(cur);
return;
}
if(!ch[rt][1])
{
int cur = rt;
rt = ch[rt][0];
fa[rt] = 0;
clear(cur);
return;
}
int cur = rt , x = pre();
fa[ch[cur][1]] = x;
ch[x][1] = ch[cur][1];
clear(cur);
maintain(rt);
return;
}
}tree;
int main()
{
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
while(n--)
{
cin >> x;
tree.ins(x);
}
while(m--)
{
cin >> op >> x;
x ^= last;
if(op == '1')
{
tree.ins(x);
}
else if(op == '2')
{
tree.del(x);
}
else if(op == '3')
{
last = tree.rk(x);
}
else if(op == '4')
{
last = tree.kth(x);
}
else if(op == '5')
{
tree.ins(x);
last = val[tree.pre()];
tree.del(x);
}
else if(op == '6')
{
tree.ins(x);
last = val[tree.nxt()];
tree.del(x);
}
ans ^= last;
}
cout << ans;
return 0;
}
```
还有就是异或和这部分可能也有点问题，求条