seuOJ422 - 简单平衡树

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：2000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 初赛, 2022

题目描述

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

• 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
0
-1
10

数据范围与提示

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

1 10
4 4
2 6
1 9
3 1
2 10
4 1
1 10
2 7
3 3

数据范围：
对于全部的数据， $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，这只是为了更好地展示数据的生成方式，所有测试点中的数据全部是合法的。

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