FHQ 玄关求调
查看原帖
FHQ 玄关求调
891062
Ericzc楼主2025/1/12 10:16

今天写了个 FHQ 只有 14 分,又蛙又 T ,下载数据结果就是样例,蒟蒻代码如下,哪位大佬能帮我调一下:

#include<bits/stdc++.h>

using namespace std;

struct node
{
	int ls, rs;
	int key, pri;
	int size;
};

int n;
node tree[100010];
int idx;
int root;

void add_node(int x)
{
	idx ++;
	tree[idx].ls = tree[idx].rs = 0;
	tree[idx].key = x;
	tree[idx].pri = rand();
	tree[idx].size = 1;
}

void update(int u)
{
	tree[u].size = tree[tree[u].ls].size + tree[tree[u].rs].size + 1;
}

void split(int u, int x, int &L, int &R)
{
	if(u == 0)
	{
		L = R = 0;
		return;
	}
	if(tree[u].key <= x)
	{
		L = u;
		split(tree[u].rs, x, tree[u].rs, R);
	}
	else
	{
		R = u;
		split(tree[u].ls, x, L, tree[u].ls);
	}
}

int merge(int L, int R)
{
	if(L == 0) return R;
	if(R == 0) return L;
	if(tree[L].pri > tree[R].pri)
	{
		tree[L].rs = R;
		update(L);
		return L;
	}
	else
	{
		tree[R].ls = L;
		update(R);
		return R;
	}
}

void insert(int x)
{
	int l, r;
	split(root, x, l, r);
	add_node(x);
	int kkk = merge(l, idx);
	root = merge(kkk, r);
}

void del(int x)
{
	int l, r, p;
	split(root, x, l, r);
	split(root, x - 1, l, p);
	p = merge(tree[p].ls, tree[p].rs);
	root = merge(merge(l, p), r);
}

void rk(int x)
{
	int l, r;
	split(root, x - 1, l, r);
	cout << tree[l].size + 1 << "\n";
	root = merge(l, r);
}

int kth(int u, int x)
{
	if(x == tree[tree[u].ls].size + 1) return u;
	else if(tree[tree[u].ls].size >= x)
	{
		return kth(tree[u].ls, x);
	}
	else
	{
		return kth(tree[u].rs, x - tree[tree[u].ls].size - 1);
	}
}

void pre(int x)
{
	int l, r;
	split(root, x - 1, l, r);
	cout << tree[kth(l, tree[l].size)].key << "\n";
	root = merge(l, r);
}

void nex(int x)
{
	int l, r;
	split(root, x, l, r);
	cout << tree[kth(r, 1)].key << "\n";
	root = merge(l, r);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++)
	{
		int op, x;
		cin >> op >> x;
		if(op == 1) insert(x);
		else if(op == 2) del(x);
		else if(op == 3) rk(x);
		else if(op == 4) cout << tree[kth(root, x)].key << "\n";
		else if(op == 5) pre(x);
		else nex(x);
	}
	return 0;
}
2025/1/12 10:16
加载中...