orz
by impuk @ 2020-05-02 16:46:15
>orz
？？？
by LJC00175 @ 2020-05-02 16:46:48
@[LJC00175](/user/91819) 样例没问题，只是数据有点玄学
by andyli @ 2020-05-02 16:48:20
[评测记录](https://www.luogu.com.cn/record/33284995)
这份代码样例没过，然而AC了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100000 + 5, INF = 0x7fffffff;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct Treap {
int l, r;
int val, dat;
int cnt, size;
};
Treap a[SIZE];
int tot, root, n;
int New(int val) {
tot++;
a[tot].val = val;
a[tot].dat = rand();
a[tot].cnt = a[tot].size = 1;
return tot;
}
void update(int p) {
a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
void build() {
New(-INF); New(INF);
root = 1; a[1].r = 2;
update(root);
}
int getrank(int p, int val) {
if(p == 0) return 0;
if(val == a[p].val) return a[a[p].l].size + 1;
if(val < a[p].val) return getrank(a[p].l, val);
return getrank(a[p].r, val) + a[a[p].l].size + a[p].cnt;
}
int getval(int p, int rank) {
if(p == 0) return INF;
if(a[a[p].l].size >= rank) return getval(a[p].l, rank);
if(a[a[p].l].size + a[p].cnt >= rank) return a[p].val;
return getval(a[p].r, rank - a[a[p].l].size - a[p].cnt);
}
void zig(int &p) {
int q = a[p].l;
a[p].l = a[q].r; a[q].r = p; p = q;
update(a[p].r); update(p);
}
void zag(int &p) {
int q = a[p].r;
a[p].r = a[q].l; a[q].l = p; p = q;
update(a[p].l); update(p);
}
void insert(int &p, int val) {
if(p == 0) {
p = New(val);
return;
}
if(val == a[p].val) {
a[p].cnt++; update(p);
return;
}
if(val < a[p].val) {
insert(a[p].l, val);
if(a[p].dat < a[a[p].l].dat) zig(p);
}
else {
insert(a[p].r, val);
if(a[p].dat < a[a[p].r].dat) zag(p);
}
update(p);
}
int getpre(int val) {
int ans = 1;
int p = root;
while(p) {
if(val == a[p].val) {
if(a[p].l > 0) {
p = a[p].l;
while(a[p].r > 0) p = a[p].r;
ans = p;
}
break;
}
if(a[p].val < val && a[p].val > a[ans].val) ans = p;
p = val < a[p].val ? a[p].l : a[p].r;
}
return a[ans].val;
}
int getnext(int val) {
int ans = 2;
int p = root;
while(p) {
if(val == a[p].val) {
if(a[p].r > 0) {
p = a[p].r;
while(a[p].l > 0) p = a[p].l;
ans = p;
}
break;
}
if(a[p].val > val && a[p].val < a[ans].val) ans = p;
p = val < a[p].val ? a[p].l : a[p].r;
}
return a[ans].val;
}
void remove(int &p, int val) {
if(p == 0) return;
if(val == a[p].val) {
if(a[p].cnt > 1) {
a[p].cnt--; update(p);
return;
}
if(a[p].l || a[p].r) {
if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat) {
zig(p); remove(a[p].r, val);
}
else {
zag(p); remove(a[p].l, val);
}
update(p);
}
else p = 0;
return;
}
val < a[p].val ? remove(a[p].l, val) : remove(a[p].r, val);
update(p);
}
int main() {
n = read();
build();
while(n--) {
int opt, x;
opt = read(); x = read();
if(opt == 1) printf("%d\n", getrank(root, x));
else if(opt == 2) printf("%d\n", getval(root, x+1));
else if(opt == 3) printf("%d\n", getpre(x));
else if(opt == 4) printf("%d\n", getnext(x));
else if(opt == 5) insert(root, x);
}
return 0;
}
```
by LJC00175 @ 2020-05-02 16:48:38
@[LJC00175](/user/91819) <https://www.luogu.com.cn/discuss/show/220714?page=2>
by andyli @ 2020-05-02 16:48:38
所以就是数据有误？
by LJC00175 @ 2020-05-02 16:49:02