rt

其实WA一堆

代码照着lyd书上的对照着检查了两遍了。

#3数据本地跑的就是对的，交上去就是错的

去了ACWing交了一发，同样在这个数据，开了srand(time(0)）就过了这个点（后面又WA了），没开就WA，但是随机化的权值不是只影响结构又不会影响答案吗/kel

感觉自己代码玄学的一批，求神仙们调

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i==)
typedef long long ll;
using namespace std;
const int MAXN=1e5+10,INF=1e9;
int n,op,x;
struct Node{
	int l,r;
	int val,w,cnt,sz;
};
struct Treap{
	Node tree[MAXN];
	int tot,rt;
	int New(int val){
		tot++,tree[tot].val=val,tree[tot].w=rand();
		tree[tot].cnt=tree[tot].sz=1;
		return tot;
	}
	void push_up(int x){
		tree[x].sz=tree[x].cnt+tree[tree[x].l].sz+tree[tree[x].r].sz;
	}
	void Build(){
		tree[0].w=-1;
		New(-INF);New(INF);
		rt=1;
		tree[1].r=2;
		tree[1].w=INF; 
		push_up(1);
	}
	void zig(int& x){
		int y=tree[x].l;
		tree[x].l=tree[y].r,tree[y].r=x,x=y;
		push_up(tree[x].r),push_up(x);
	}
	void zag(int& x){
		int y=tree[x].r;
		tree[x].r=tree[y].l,tree[y].l=x,x=y;
		push_up(tree[x].l),push_up(x); 
	}
	int getRank(int x,int val){
		if(!x)return 0;
		if(tree[x].val==val)return tree[tree[x].l].sz+1;
		if(val<tree[x].val)return getRank(tree[x].l,val);
		else return tree[tree[x].l].sz+tree[x].cnt+getRank(tree[x].r,val); 
	}
	int getVal(int x,int rank){
		if(!x)return INF;
		if(tree[tree[x].l].sz>=rank)return getVal(tree[x].l,rank);
		else if(tree[tree[x].l].sz+tree[x].cnt>=rank)return tree[x].val;
		else return getVal(tree[x].r,rank-tree[tree[x].l].sz-tree[x].cnt);
	}
	void insert(int& x,int val){
		if(!x){x=New(val);return;}
		if(tree[x].val==val){tree[x].cnt++;push_up(x);return;}
		if(val<tree[x].val){
			insert(tree[x].l,val);
			if(tree[x].w<tree[tree[x].l].w)zig(x);
		}else{
			insert(tree[x].r,val);
			if(tree[x].w<tree[tree[x].r].w)zag(x);
		}
		push_up(x);
	}
	void pop(int& x,int val){
		if(!x)return;
		if(tree[x].val==val){
			if(tree[x].cnt>1){
				tree[x].cnt--;
				push_up(x);
				return;
			}
			if(tree[x].l || tree[x].r){
				if(!tree[x].r || tree[tree[x].l].w>tree[tree[x].r].w){
					zig(x);pop(tree[x].r,val);
				}else{
					zag(x);pop(tree[x].l,val);
				}
			}else x=0;
			return;
		}
		if(val<tree[x].val)pop(tree[x].l,val);
		else pop(tree[x].r,val);
		push_up(x);
	}
	int getpre(int val){
		int ans=1,p=rt;
		while(p){
			if(val==tree[p].val){
				if(tree[p].l){
					p=tree[p].l;
					while(tree[p].r)p=tree[p].r;
					ans=p;
				}
				break;
			}
			if(tree[p].val<val && tree[p].val>tree[ans].val)ans=p;
			if(val<tree[p].val)p=tree[p].l;
			else p=tree[p].r;
		}
		return tree[ans].val;
	}
	int getnext(int val){
		int ans=2,p=rt;
		while(p){
			if(val==tree[p].val){
				if(tree[p].r){
					p=tree[p].r;
					while(tree[p].l)p=tree[p].l;
					ans=p;
				}
				break;
			}
			if(tree[p].val>val && tree[p].val<tree[ans].val)ans=p;
			if(val<tree[p].val)p=tree[p].l;
			else p=tree[p].r;
		}
		return tree[ans].val;
	}
}treap;
int main(){
//	freopen("P3369_3.in","r",stdin);
//	freopen("out.out","w",stdout);
	scanf("%d",&n);
	treap.Build();
	rep(i,1,n){
		scanf("%d%d",&op,&x);
		if(op==1){
			treap.insert(treap.rt,x);
		}else if(op==2){
			treap.pop(treap.rt,x);
		}else if(op==3){
			printf("%d\n",treap.getRank(treap.rt,x)-1);
		}else if(op==4){
			printf("%d\n",treap.getVal(treap.rt,x+1));
		}else if(op==5){
			printf("%d\n",treap.getpre(x));
		}else{
			printf("%d\n",treap.getnext(x));
		}
	}
	return 0;
} 

另：#3数据：

in：

50
1 577793
1 408221
1 880861
2 408221
1 460353
1 223489
6 577713
4 2
5 889905
2 880861
1 100033
1 73956
1 22575
5 583761
6 571549
1 812645
4 3
1 643621
1 451623
6 14895
1 556691
4 1
1 225789
2 22575
1 632329
3 73956
1 316785
5 101413
4 11
5 639414
6 636353
1 272382
1 434049
2 643621
1 99617
2 577793
1 921581
1 894033
3 223489
1 767367
3 272382
1 642721
1 272033
3 632329
1 737721
1 864513
5 746457
1 877545
1 51097
1 484817

out：

577793
460353
880861
577793
577793
100033
22575
22575
1
100033
643621
632329
643621
4
6
13
737721

感激不尽