May_Cry_ @ 2023-09-21 19:44:58
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1e6 + 7;
int n ,m ,root ,tot ,last ,ans;
mt19937 rd(20100222);
struct node {
int l ,r;
int size ,val ,key;
}T[N];
int add(int v){
T[++ tot].val = v;
T[tot].key = rd();
T[tot].size = 1;
return tot;
}
void pushup(int i){
T[i].size = T[T[i].l].size + T[T[i].r].size + 1;
}
int merge(int x ,int y){
if (!x || !y) return x | y;
if (T[x].key <= T[y].key){
T[x].r = merge(T[x].r ,y);
pushup(x);
return x;
}
else{
T[y].l = merge(x ,T[y].l);
pushup(y);
return y;
}
}
void split (int p ,int val ,int &x ,int &y){
if (!p) x = y = 0;
else{
if (T[p].val <= val){
x = p ,split(T[x].r ,val ,T[x].r ,y);
}
else {
y = p ,split(T[y].l ,val ,x ,T[y].l);
}
pushup(p);
}
}
int query(int p ,int k){
if (T[T[p].l].size + 1 == k) return T[p].val;
if (k <= T[T[p].l].size) return query (T[p].l ,k);
else return query (T[p].r ,k - T[T[p].l].size - 1);
}
int read();
int main(){
n = read() ,m = read();
for (int i = 1;i <= n;i ++) {
int x = read();int l ,r;
split(root ,x ,l ,r);
root = merge(merge(l ,add(x)) ,r);
}
while (m --){
int op = read() ,x = read();
x = x ^ last;
if(op == 1) {
int l ,r;
split(root ,x ,l ,r);
root = merge(merge(l ,add(x)) ,r);
}
if(op == 2){
int g ,l ,r;
split(root ,x ,l ,r);
split(root ,x - 1 ,l ,g);
g = merge(T[g].l ,T[g].r);
root = merge(merge(l ,g) ,r);
}
if(op == 3){
int l ,r;
split(root ,x - 1 ,l ,r);
last = T[l].size + 1;
ans ^= last;
// cout << last << endl;
root = merge(l ,r);
}
if(op == 4){
last = query(root ,x);
// cout << last << endl;
ans ^= last;
}
if(op == 5){
int l ,r;
split(root ,x - 1 , l, r);
last = query(l ,T[l].size);
// cout << last << endl;
ans ^= last;
root = merge(l ,r);
}
if(op == 6){
int l ,r;
split(root ,x ,l ,r);
last = query(r ,1);
ans ^= last;
// cout << last << endl;
root = merge(l ,r);
}
}
cout << ans;
return 0;
}
int read(){
int x = 0 ,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}by May_Cry_ @ 2023-09-21 19:47:48
调出来了，此贴结，是删除的问题
by May_Cry_ @ 2023-09-21 19:48:03
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1e6 + 7;
int n ,m ,root ,tot ,last ,ans;
mt19937 rd(20100222);
struct node {
int l ,r;
int size ,val ,key;
}T[N];
int add(int v){
T[++ tot].val = v;
T[tot].key = rd();
T[tot].size = 1;
return tot;
}
void pushup(int i){
T[i].size = T[T[i].l].size + T[T[i].r].size + 1;
}
int merge(int x ,int y){
if (!x || !y) return x | y;
if (T[x].key <= T[y].key){
T[x].r = merge(T[x].r ,y);
pushup(x);
return x;
}
else{
T[y].l = merge(x ,T[y].l);
pushup(y);
return y;
}
}
void split (int p ,int val ,int &x ,int &y){
if (!p) x = y = 0;
else{
if (T[p].val <= val){
x = p ,split(T[x].r ,val ,T[x].r ,y);
}
else {
y = p ,split(T[y].l ,val ,x ,T[y].l);
}
pushup(p);
}
}
int query(int p ,int k){
if (T[T[p].l].size + 1 == k) return T[p].val;
if (k <= T[T[p].l].size) return query (T[p].l ,k);
else return query (T[p].r ,k - T[T[p].l].size - 1);
}
int read();
int main(){
n = read() ,m = read();
for (int i = 1;i <= n;i ++) {
int x = read();int l ,r;
split(root ,x ,l ,r);
root = merge(merge(l ,add(x)) ,r);
}
while (m --){
int op = read() ,x = read();
x = x ^ last;
if(op == 1) {
int l ,r;
split(root ,x ,l ,r);
root = merge(merge(l ,add(x)) ,r);
}
if(op == 2){
int g ,l ,r;
split(root ,x ,l ,r);
split(l ,x - 1 ,l ,g);
g = merge(T[g].l ,T[g].r);
root = merge(merge(l ,g) ,r);
}
if(op == 3){
int l ,r;
split(root ,x - 1 ,l ,r);
last = T[l].size + 1;
ans ^= last;
// cout << last << endl;
root = merge(l ,r);
}
if(op == 4){
last = query(root ,x);
// cout << last << endl;
ans ^= last;
}
if(op == 5){
int l ,r;
split(root ,x - 1 , l, r);
last = query(l ,T[l].size);
// cout << last << endl;
ans ^= last;
root = merge(l ,r);
}
if(op == 6){
int l ,r;
split(root ,x ,l ,r);
last = query(r ,1);
ans ^= last;
// cout << last << endl;
root = merge(l ,r);
}
}
cout << ans;
return 0;
}
int read(){
int x = 0 ,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}