简单平衡树 - 题目

传统 2000 ms 256 MiB

标准 IO

文本比较 dd 标签

提交记录统计测试数据讨论

在本题中，你需要维护一个数据结构，完成平衡搜索树的几种操作。

1 x：插入数字 $x$ 。
2 x：删除数字 $x$ （ $x$ 不存在则忽略）。
3 x：查询当前第 $x$ 小的数字(下标从 $1$ 开始，重复的也计算，比如有平衡搜索树中有元素 $1,2,2,4,4,6$ ，那么第 $3$ 小的数字为 $2$ )。
4 x：查询数字 $x$ 的排名（从小到大，从1开始，若 $x$ 不存在则输出-1，比如有平衡搜索树中有元素 $1,2,2,4,4,6$ ，那么数字 $4$ 的排名为 $4$ ）。

请注意：

平衡搜索树初始时不为空，其中初始时有一个元素0,即你在程序开头需要向你写的数据结构中先插入一个0。
如果删除失败，不要把sum-1；如果删除成功，一定要把sum-1。

如果你不注意以上两点，你的代码可能会得到错误的结果。

本题目输入数据量较大，输入数据采取如下方式生成：

输入仅有一行，包含 $4$ 个整数：m seed vmax per
分别代表操作数，随机数种子， $x$ 的上限，操作 $1,2$ 所占比例。

你应该按照如下方式完成程序：

#include<iostream>
//include headfiles you need
using namespace std;
typedef unsigned int unit;

int m, vmax, per;

unit seed;
unit rnd(unit& seed) {
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

//you do it...
int main() {
	//!insert 0
	int sum = 1;
	cin >> m >> seed >> vmax >> per;
	for (int i = 1; i <= m; i++) {
		int op = rnd(seed) % 100 + 1;
		if (op <= per) {
			int x = rnd(seed) % vmax + 1;
			if (op % 2 == 0) {
				//finish op 1
				++sum;
			}
			else {
				//finish op 2
				//--sum if x is exists
			}
		}
		else {
			if (op % 2 == 0) {
				int x = rnd(seed) % sum + 1;
				//finish op 3
			}
			else {
				int x = rnd(seed) % vmax + 1;
				//finish op 4
			}
		}
	}
	return 0;
}

对于每次操作 $3$ 或操作 $4$ 输出一行数字表示答案。

输入样例：

10 521 10 50

输出样例：

样例解释：
样例 $1$ 的所有操作为：

数据范围：
对于全部的数据， $1\leq m \leq 10^7$ , $1\leq seed \leq 10^9$ , $1\leq vmax\leq 5\times10^5$ , $95\leq per \leq 100$ 。

注：尽管样例的per=50，这只是为了更好地展示数据的生成方式，所有测试点中的数据全部是合法的。

请注意此题较为特殊的时间限制。

#422. 简单平衡树

题目描述

输入格式

输出格式

样例

数据范围与提示