P6136平衡树加强版。
P3369（普通平衡树）过了
蒟蒻写了好久已经崩溃力
#include<bits/stdc++.h>
#define int long long
#define INF 1e19
using namespace std;
const int N = 2e7 + 10;
int tot = 0, root = 0;
int ans = 0 ;
struct node {
int data, heep, left, right, size, cnt;
} dt[N];
int new_node(int data) {
dt[++tot].data = data;
dt[tot].heep = rand();
dt[tot].left = dt[tot].right = 0;
dt[tot].size = dt[tot].cnt = 1;
return tot;
}
void build() {
root = new_node(-INF) ;
dt[root].right = new_node(INF) ;
dt[ dt[ root ].right ].heep = dt[ root ].heep + 1 ;
dt[root].size = 2;
}
void right_change(int &now_lo) {
int p = dt[now_lo].right;
dt[now_lo].right = dt[p].left;
dt[p].left = now_lo;
dt[now_lo].size = dt[dt[now_lo].left].size + dt[dt[now_lo].right].size + dt[now_lo].cnt;
dt[p].size = dt[dt[p].left].size + dt[dt[p].right].size + dt[p].cnt;
now_lo = p;
}
void left_change(int &now_lo) {
int p = dt[now_lo].left;
dt[now_lo].left = dt[p].right;
dt[p].right = now_lo;
dt[now_lo].size = dt[dt[now_lo].left].size + dt[dt[now_lo].right].size + dt[now_lo].cnt;
dt[p].size = dt[dt[p].left].size + dt[dt[p].right].size + dt[p].cnt;
now_lo = p;
}
void insert(int &now_lo, int data) {
if (now_lo == 0) {
now_lo = new_node(data);
return;
} else if (dt[now_lo].data == data) {
dt[now_lo].cnt++;
} else if (data < dt[now_lo].data) {
insert(dt[now_lo].left, data);
if (dt[dt[now_lo].left].heep > dt[now_lo].heep) left_change(now_lo);
} else {
insert(dt[now_lo].right, data);
if (dt[dt[now_lo].right].heep > dt[now_lo].heep) right_change(now_lo);
}
dt[now_lo].size = dt[dt[now_lo].left].size + dt[dt[now_lo].right].size + dt[now_lo].cnt;
}
void delate(int &now_lo, int data) {
if (now_lo == 0) return;
if (dt[now_lo].data > data) {
delate(dt[now_lo].left, data);
} else if (dt[now_lo].data < data) {
delate(dt[now_lo].right, data);
} else {
if (dt[now_lo].cnt > 1) {
dt[now_lo].cnt--;
} else if (dt[now_lo].left == 0 && dt[now_lo].right == 0) {
now_lo = 0;
} else if (dt[now_lo].left == 0 || (dt[now_lo].right && dt[dt[now_lo].right].heep > dt[dt[now_lo].left].heep)) {
right_change(now_lo);
delate(dt[now_lo].left, data);
} else {
left_change(now_lo);
delate(dt[now_lo].right, data);
}
}
if (now_lo != 0) dt[now_lo].size = dt[dt[now_lo].left].size + dt[dt[now_lo].right].size + dt[now_lo].cnt;
}
int askfront( int now_lo , int data )
{
if( now_lo == 0 ) return - INF ;
else if( dt[ now_lo ].data >= data )
return askfront( dt[ now_lo ].left , data ) ;
else return max( dt[ now_lo ].data , askfront( dt[ now_lo ].right , data ) ) ;
}
int askback( int now_lo , int data) {
if( now_lo == 0 ) return INF ;
else if( dt[ now_lo ].data <= data )
return askback( dt[ now_lo ].right , data ) ;
else return max( dt[ now_lo ].data , askback( dt[ now_lo ].left , data ) ) ;
}
int askval(int now_lo, int data) {
if (now_lo == 0) return 1;
if (dt[now_lo].data == data) return dt[dt[now_lo].left].size + 1;
else if (dt[now_lo].data < data) return dt[dt[now_lo].left].size + dt[now_lo].cnt + askval(dt[now_lo].right, data);
else return askval(dt[now_lo].left, data);
}
int asklast(int now_lo, int data) {
if (now_lo == 0) return 0;
if (data <= dt[dt[now_lo].left].size) return asklast(dt[now_lo].left, data);
else if (data <= dt[dt[now_lo].left].size + dt[now_lo].cnt) return dt[now_lo].data;
else return asklast( dt[now_lo].right, data - dt[dt[now_lo].left].size - dt[now_lo].cnt ) ;
}
signed main() {
// freopen("P6136_5.in" , "r" , stdin ) ;
srand((unsigned)time(0));
build();
int n , m , last = 0 ;
cin >> m >> n ;
for( int i = 1 ; i <= m ; i ++ )
{
int d ;
cin >> d ;
insert( root , d ) ;
}
for ( int i = 1; i <= n; i++) {
int T, x;
cin >> T >> x ;
x = x ^ last ;
if (T == 1) insert(root, x);
else if (T == 2) delate(root, x);
else if (T == 3) last = askval( root , x ) - 1 ;
else if (T == 4) last = asklast( root , x + 1 ) ;
else if (T == 5) last = askfront( root , x ) ;
else if (T == 6) last = askback( root , x ) ;
ans = ans ^ last ;
}
cout << ans ;
return 0;
}