普通平衡树(数据加强版)

链接

题目差不多,无非就是设两个变量(但是m怎么有1e6啊,害得我re了两次)

#include<iostream>
#include<random>
using namespace std;
const int MAXN = 2e5 + 5;
#define ll long long
struct node{
	int l, r;
	ll val;
	int size;
}fhq[MAXN];
int cnt, root;
int newnode(ll val) {
	fhq[++cnt] = { 0,0,val,1 };
	return cnt;
}
void update(int x) {
	fhq[x].size = fhq[fhq[x].l].size + fhq[fhq[x].r].size + 1;
}
void split(int now, ll val, int& x, int& y) {
	if (!now) x = y = 0;
	else {
		if (fhq[now].val <= val) {
			x = now;
			split(fhq[now].r, val, fhq[x].r, y);
		}
		else {
			y = now;
			split(fhq[now].l, val, x, fhq[now].l);
		}
		update(now);
	}
}
int merge(int x,int y) {
	if (!x || !y) return x + y;
	if (rand() % (fhq[x].size + fhq[y].size) < fhq[x].size) {
		fhq[x].r = merge(fhq[x].r, y);
		update(x);
		return x;
	}
	else {
		fhq[y].l = merge(x, fhq[y].l);
		update(y);
		return y;
	}
}
int x, y, z;
void ins(int val) {
	split(root, val, x, y);
	x = merge(x, newnode(val));
	root = merge(x, y);
}
void del(ll val) {
	split(root,val, x, z);
	split(x, val - 1, x, y);
	y = merge(fhq[y].l, fhq[y].r);
	root = merge(merge(x, y), z);
}
int getrank(ll val) {
	split(root, val - 1, x, y);
	int ans = fhq[x].size + 1;
	root = merge(x, y);
	return ans;
}
ll getnum(int rk) {
	int now = root;
	while (now) {
		if (fhq[fhq[now].l].size + 1 == rk) return fhq[now].val;
		else if (fhq[fhq[now].l].size >= rk) now = fhq[now].l;
		else {
			rk -= fhq[fhq[now].l].size + 1;
			now = fhq[now].r;
		}
	}
	return -2e8;
}
ll pre(ll val) {
	split(root, val - 1, x, y);
	int now = x;
	while (now && fhq[now].r) now = fhq[now].r;
	ll ans = fhq[now].val;
	root = merge(x, y);
	return ans;
}
ll nxt(ll val) {
	split(root, val, x, y);
	int now = y;
	while (now && fhq[now].l) now = fhq[now].l;
	ll ans = fhq[now].val;
	root = merge(x, y);
	return ans;
}
int main() {
	srand(time(0));
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		ll num;
		cin >> num;
		ins(num);
	}
	ll last = 0;
	ll answer = 0;
	while (m--) {
		int opt;
		ll x;
		cin >> opt >> x;
		x = x ^ last;
		if (opt == 1) ins(x);
		else if (opt == 2) del(x);
		else if (opt == 3) {
			last = getrank(x);
			answer ^= last;
		}
		else if (opt == 4) {
			last = getnum(x);
			answer ^= last;
		}
		else if (opt == 5) {
			last = pre(x);
			answer ^= last;
		}
		else {
			last = nxt(x);
			answer ^= last;
		}
	}
	cout << answer;
}

时间复杂度:O((n+m) log (n+m))

空间复杂度:O(n + m)