U156719 Dynamic Predecessor Problem
题目背景
# 2022/04/02 update：据说数据出了大锅，可惜本人已经退役可能没法修了，给大家造成的困扰还请谅解。
2021/11/14 update：被用户 [123456zmy](https://www.luogu.com.cn/user/44840) 指出数据生成器存在一定问题，进行了修改并开大了时限，感谢他的指出。
我的[《压位 Trie 学习笔记》](https://www.luogu.com.cn/blog/DPair2005/ya-wei-trie-xue-xi-bi-ji)配套试题
我已经尽可能减小随机数生成器的常数了，但是再卡下去生成出来的随机数就会极其不均匀。
std 的运行时间在 2s 以内。
题目描述
写一种数据结构,来维护一些数,其中需要支持以下操作:
0. 插入 $x$ 数(若已有 $x$ 则不进行此操作);
1. 删除 $x$ 数(若 $x$ 不存在则不进行此操作);
2. 求 $x$ 的前趋(前趋定义为 **小于** $x$,且最大的数,若不存在则答案为 $0$);
3. 求 $x$ 的后继(后继定义为 **大于** $x$,且最小的数,若不存在则答案为 $0$);
输入格式
无
输出格式
无
说明/提示
**本题采用捆绑测试，你只有通过了一个 Subtask 下的所有数据才能得到对应的分数。**
对于 $100\%$ 的数据，满足 $0\le seed, x< 2^{30}$ 。
对于 $20\%$ 的数据，满足 $1 \le n \le 10^6$，时限 1.5s。
另有 $40\%$ 的数据，满足 $1 \le n \le 5 \times10^6$，时限 1.5s。
另有 $40\%$ 的数据，满足 $1 \le n \le 3\times 10^7$ ，时限 3s。
模板如下（把lxl的随机数生成器砍了一大截）：
```cpp
#include
namespace GenHelper{
unsigned z3, z4, b;
inline unsigned rand_(){
z3 = ((z3 & 4294967280U) 21;
z4 = ((z4 & 4294967168U) 12;
return (z3 ^ z4);
}
}
inline void srand_(unsigned x){
using namespace GenHelper;
z3 = x ^ 0x1234598766U;
z4 = (~x) + 51;
}
int ans;
inline void work(){
int x = GenHelper::rand_() & ((1 > 15) & 3;
/* Your code begins here */
}
int n, seed;
int main(){
scanf("%d%d", &n, &seed);
srand_(seed);
while(n --) work();
printf("%d\n", ans);
}
```
另附一个供参考的 `std::set` 模板（只能通过 20pts） ：
```cpp
#include
namespace GenHelper{
unsigned z3, z4, b;
inline unsigned rand_(){
z3 = ((z3 & 4294967280U) 21;
z4 = ((z4 & 4294967168U) 12;
return (z3 ^ z4);
}
}
inline void srand_(unsigned x){
using namespace GenHelper;
z3 = x ^ 0x1234598766U;
z4 = (~x) + 51;
}
int ans;
#include
using std :: set;
set s;
inline void work(){
int x = GenHelper :: rand_() & ((1 > 15) & 3;
/* Your code begins here */
if(op == 0) s.insert(x);
else if(op == 1) s.erase(x);
else if(op == 2) {
auto it = s.lower_bound(x);
if(it != s.begin()) ans ^= *(-- it);
}
else {
auto it = s.upper_bound(x);
if(it != s.end()) ans ^= *it;
}
}
int n, seed;
int main(){
scanf("%d%d", &n, &seed);
srand_(seed);
while(n --) work();
printf("%d\n", ans);
}
```