记录详情

#include <bits/stdc++.h>
#define lc(x) tre[x].lc
#define rc(x) tre[x].rc
#define siz(x) tre[x].siz
#define val(x) tre[x].val
#define key(x) tre[x].key 

using namespace std;

const int N = 2e6 + 5;

int n, m, tot, last, ans, rot, l, r;

struct node{
	int val, key;
	int siz;
	int lc, rc;
}tre[N];

int get_rand(){
	return rand();	
}

void pushup(int u){ siz(u) = siz(lc(u)) + siz(rc(u)) + 1; }

int newnode(int val){
	++ tot;
	lc(tot) = rc(tot) = 0;
	val(tot) = val;
	siz(tot) = 1;
	key(tot) = get_rand();
	return tot;
}

void split(int u, int x, int &l, int &r){
	if(!u){
		l = r = 0;
		return ;
	}
	if(val(u)<=x){
		l = u;
		split(rc(u), x, rc(u), r);
	}else{
		r = u;
		split(lc(u), x, l, lc(u));	
	}
	pushup(u);
}

int merge(int u, int v){
	if(!u || !v)
		return u | v;
	if(key(u) <= key(v)){
		rc(u) = merge(rc(u), v);
		pushup(u);
		return u;
	}else{
		lc(v) = merge(u, lc(v));
		pushup(v);
		return v;	
	}
}

int kth(int u, int k){
	if(k <= siz(lc(u)))
		return kth(lc(u), k);
	else if(k == siz(lc(u)) + 1)
		return u;
	else{
		k -= (siz(lc(u)) + 1);
		return kth(rc(u), k);
	}
}

int main(){
	srand(time(0));
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i){
		int a;
		scanf("%d", &a);
		rot = merge(newnode(a), rot);
	}
	for(int i = 1; i <= m; ++i){
		int op, x;
		scanf("%d %d", &op, &x);
		x ^= last;
		if(op == 1){
			split(rot, x, l, r);
			newnode(x);
			rot = merge(merge(l, tot), r);
		}
		if(op == 2){
			int p;
			split(rot, x, l, r);
			split(l, x - 1, l, p);
			p = merge(lc(p), rc(p));
			rot = merge(merge(l, p), r);
		}
		if(op == 3){
			split(rot, x - 1, l, r);
			last = siz(l) + 1;
			ans ^= last;
			rot = merge(l, r);
		}
		if(op == 4){
			last = val(kth(rot, x));
			ans ^= last;
		}
		if(op == 5){
			split(rot, x - 1, l, r);
			last = val(kth(l, siz(l)));
			ans ^= last;
			rot = merge(l, r);
		}
		if(op == 6){
			split(rot, x, l, r);
			last = val(kth(r, 1));
			ans ^= last;	
			rot = merge(l, r);
		}
	}
	printf("%d\n", ans);
	return 0;	
}