@[路人甲2003](/space/show?uid=149168) 不开static可海星
by YLWang @ 2019-06-13 19:25:27
@[路人甲2003](/space/show?uid=149168) 应该是tot没有置0？没跑过看看的，不知道是不是
by YLWang @ 2019-06-13 19:26:18
~~封装我可不会~~
by YLWang @ 2019-06-13 19:28:26
@[破壁人四号](/space/show?uid=55078) 不行
by 路人甲2003 @ 2019-06-15 23:04:03
```
#include<bits/stdc++.h>
using namespace std;
struct Node{
int l, r;
int val, dat;
int cnt, size;
};
struct Treap{
Node a[100005];
int tot = 0, root, n, INF=0x7ffffff;
inline int New(int val) {
a[++tot].val = val;
a[tot].dat = rand();
a[tot].cnt = a[tot].size = 1;
return tot;
}
inline void update(int p) {
a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
inline void build() {
New(-INF), New(INF);
root = 1;
a[1].r = 2;
update(root);
}
inline int grbv(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 grbv(a[p].l, val);
return grbv(a[p].r, val) + a[a[p].l].size + a[p].cnt;
}
inline int gvbr(int p, int rank) {
if(p == 0) return INF;
if(a[a[p].l].size >= rank) return gvbr(a[p].l, rank);
if(a[a[p].l].size + a[p].cnt >= rank) {return a[p].val;}
return gvbr(a[p].r, rank - a[a[p].l].size - a[p].cnt );
}
inline 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);
}
inline 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);
}
inline 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);
}
inline 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) 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;
}
inline int getnxt(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) 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;
}
inline 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].r, val);
}
else p=0;
}
val < a[p].val ? remove(a[p].l, val) : remove(a[p].r, val);
update(p);
}
}tree;
int main(){
srand(10);
tree.build();
int n,x,y;
cin >> n;
for(int i=1;i<=n;++i) {
//x=read();y=read();
scanf("%d%d",&x,&y);
switch(x){
case 1:
tree.Insert(tree.root, y);
break;
case 2:
tree.remove(tree.root, y);
break;
case 3:
printf("%d\n", tree.grbv(tree.root, y) - 1);
break;
case 4:
printf("%d\n", tree.gvbr(tree.root, y + 1));
break;
case 5:
printf("%d\n", tree.getpre(y));
break;
case 6:
printf("%d\n", tree.getnxt(y));
break;
}
}
return 0;
}
```
emm...
首先是main()，操作的数是x不是y；
然后是remove写错了，请回去看书；
然后是getnxt写错了，请回去看书；
以后打代码认真些呵。
by zty111 @ 2019-06-16 19:40:37
@[zty111](/space/show?uid=126692) 谢谢dalao
by 路人甲2003 @ 2019-06-16 23:11:08