@[wjh2022](/user/527206)
code:
```cpp
//#pragma GCC optimize (2)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 2147483647;
int read ()
{
int x = 0, y = 1;
char c = getchar ();
while (c < '0' || c > '9')
{
if (c == '-') y = -1;
c = getchar ();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + c - '0';
c = getchar ();
}
return x * y;
}
void write (int x)
{
if (x < 0) putchar ('-'), x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
}
int q, res, root;
struct node
{
int l, r;
int key, val;
int sz, cnt;
};
node a[N];
struct Treap
{
void push_up (int p)
{
a[p].sz = a[a[p].l].sz + a[a[p].r].sz + a[p].cnt;
}
void zig (int &p)
{
int q = a[p].l;
a[p].l = a[q].r, a[q].r = p, p = q;
push_up (a[p].r), push_up (p);
}
void zag (int &p)
{
int q = a[p].r;
a[p].r = a[q].l, a[q].l = p, p = q;
push_up (a[p].l), push_up (p);
}
int make_node (int x)
{
a[ ++ res].key = x;
a[res].val = rand () * rand () + rand (), a[res].sz = a[res].cnt = 1;
return res;
}
void insert (int &p, int x)
{
if (!p) p = make_node (x);
else if (a[p].key == x) a[p].cnt ++ ;
else if (a[p].key < x)
{
insert (a[p].r, x);
if (a[p].val > a[a[p].r].val) zag (p);
}
else
{
insert (a[p].l, x);
if (a[p].val > a[a[p].l].val) zig (p);
}
push_up (p);
}
void remove (int &p, int x)
{
if (!p) return ;
else if (a[p].key == x)
{
if (a[p].cnt > 1) a[p].cnt -- ;
else if (a[p].l || a[p].r)
{
if (!a[p].r || a[a[p].l].val < a[a[p].r].val) zig (p), remove (a[p].r, x);
else zag (p), remove (a[p].l, x);
}
else p = 0;
}
else if (a[p].key < x) remove (a[p].r, x);
else remove (a[p].l, x);
push_up (p);
}
int get_rank (int p, int x)
{
if (!p) return 1;
else if (a[p].key == x) return a[a[p].l].sz + 1;
else if (a[p].key > x) return get_rank (a[p].l, x);
else return a[p].cnt + a[a[p].l].sz + get_rank (a[p].r, x);
}
int get_val (int p, int x)
{
if (a[a[p].l].sz + 1 == x) return a[p].key;
else if (a[a[p].l].sz >= x) return get_val (a[p].l, x);
else return get_val (a[p].r, x - a[a[p].l].sz - a[p].cnt);
}
int get_pre (int p, int x)
{
if (!p) return -INF;
if (a[p].key >= x) return get_pre (a[p].l, x);
else return max (a[p].key, get_pre (a[p].r, x));
}
int get_nxt (int p, int x)
{
if (!p) return INF;
if (a[p].key <= x) return get_nxt (a[p].r, x);
else return min (a[p].key, get_nxt (a[p].l, x));
}
};
Treap T;
signed main ()
{
T.insert (root, -INF), T.insert (root, INF);
q = read ();
while (q -- )
{
int opt = read (), l = read ();
if (opt == 1) T.insert (root, l);
else if (opt == 2) T.remove (root, l);
else if (opt == 3) write (T.get_rank (root, l) - 1), putchar ('\n');
else if (opt == 4) write (T.get_val (root, l + 1)), putchar ('\n');
else if (opt == 5) write (T.get_pre (root, l)), putchar ('\n');
else write (T.get_nxt (root, l)), putchar ('\n');
}
return 0;
}
```
另一个灵异的事是 65 行
```
a[res].val = rand () * rand () + rand ()
```
改为
```
a[res].val = rand ()
```
就可以过掉 #4 并获得 51 分,另外还想知道为什么 T qwq
by wjh2022 @ 2024-04-11 22:09:24
@[wjh2022](/user/527206) `rand() * rand() + rand()`爆`int`了
by PengDave @ 2024-04-11 22:25:13
爆`int`后会出现负数,把空节点上提了
by PengDave @ 2024-04-11 22:26:32
毕竟本地 windows `rand()` 的极值远比 linux 的小,所以就不会爆。
by PengDave @ 2024-04-11 22:28:49
@[PengDave](/user/1048193) 啊,好像开了 long long 了,但是您说的问题为什么真在洛谷 ide 上存在啊(
by wjh2022 @ 2024-04-11 22:39:48
说错了,是爆 `long long`
by PengDave @ 2024-04-11 22:40:27
rand 返回值貌似默认是 int
by PengDave @ 2024-04-11 22:41:40
@[wjh2022](/user/527206)
by PengDave @ 2024-04-11 22:42:06
没错,果然返回值是 `int`
by PengDave @ 2024-04-11 22:43:02
其实没爆 `long long` 但中途用 `int` 导致爆了
by PengDave @ 2024-04-11 22:43:48