玄二关,Treap WA 44pts求助
查看原帖
玄二关,Treap WA 44pts求助
510555
ImposterAnYu楼主2024/8/8 08:46

RT,目测是操作三有问题,不过也不排除前两个操作的锅

#include <bits/stdc++.h>
#define int1 int
#define N 200000
#define INF 1145141919
using namespace std;
int1 n,opt,x,rt,tot;
struct treap{
	int1 ls,rs,cnt,siz,pty,val;
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define cnt(x) tree[x].cnt
	#define pty(x) tree[x].pty
	#define siz(x) tree[x].siz
	#define val(x) tree[x].val
} tree[N + 5];
int1 read(){
	int1 x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)){
		if (ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while (isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void uprint(int1 x){
	if (x >= 10){
		uprint(x / 10);
	}
	putchar(x % 10 ^ 48);
	return ;
}
void print(int1 x){
	if (x < 0){
		putchar('-');
		x = -x;
	}
	uprint(x);
	return ;
}
void ps(int1 x){
	print(x);
	putchar(' ');
	return ;
}
void pe(int1 x){
	print(x);
	putchar('\n');
	return ;
}
int1 rd(){//随机优先级 
	return rand() * rand();
}
void upd(int1 &x){
	siz(x) = siz(ls(x)) + siz(rs(x)) + cnt(x);
}
void zig(int1 &x){//右旋 
	int1 y = ls(x);
	ls(x) = rs(y);
	rs(y) = x;
	siz(y) = siz(x);
	x = y;
	upd(rs(x));
	upd(x);
	return ;
}
void zag(int1 &x){//左旋 
	int1 y = rs(x);
	rs(x) = ls(y);
	ls(y) = x;
	siz(y) = siz(x);
	x = y;
	upd(ls(x));
	upd(x);
	return ;
}
void insert(int1 x,int1 &now){//插入 
	if(!now){//新节点
		val(now = ++tot) = x,pty(now) = rd();
		ls(now) = rs(now) = 0;
		cnt(now) = siz(now) = 1;
		return ;
	}
	siz(now)++;
	if(x == val(now)){//原有节点 
		cnt(now)++;
		return ;
	}
	if(x < val(now)){
		insert(x,ls(now));
	}else{
		insert(x,rs(now));
	}
	if(ls(now) && pty(ls(now)) < pty(now)){//调整树高 
		zig(now);
	}
	if(rs(now) && pty(rs(now)) < pty(now)){//同上 
		zag(now);
	}
	upd(now);
	return ;
}
void del(int1 x,int1 &now){//删除(应该不会有**题目删除不存在的元素吧) 
	if(!now){//找不到就润了 
		return ;
	}
	siz(now)--;
	if(x == val(now)){//找到了 
		cnt(now)--;
		if(!cnt(now)){//多个只删除一个 
			if(!ls(now) || !rs(now)){//叶子或者链节点 
				now = ls(now) + rs(now);
			}else if(pty(ls(now)) < pty(rs(now))){//左儿子优先 
				zig(now);
				del(x,now);
			}else{//右儿子优先 
				zag(now);
				del(x,now);
			}
		}
		return ;
	}
	if(x < val(now)){
		del(x,ls(now));
	}else{
		del(x,rs(now));
	}
	upd(now);
	return ;
}
int1 xrank(int1 x){//查询x的排名 
	int1 now = rt,s = 0;
	while(now){
		if(x == val(now)){
			return siz(ls(now)) + s + 1;
		}
		if(x < val(now)){ 
			now = ls(now);
		}else{
			s += siz(ls(now)) + cnt(now);
			now = rs(now);
		}
	}
	return s + 1;
}
int1 rankx(int1 x){//查询第x名的数 
	int1 now = rt;
	while(now){
		if(siz(ls(now)) < x && x <= siz(ls(now)) + cnt(now)){
			return val(now);
		}
		if(x <= siz(ls(now))){
			now = ls(now);
		}else{
			x -= siz(ls(now)) + cnt(now);
			now = rs(now);
		}
	}
	return INF;
}
int1 pre(int1 x){//查询前驱 
	int1 now = rt,s = -INF;
	while(now){
		if(val(now) < x){
			s = val(now),now = rs(now);
		}else{
			now = ls(now);
		}
	}
	return s;
}
int1 nex(int1 x){//查询后继 
	int1 now = rt,s = INF;
	while(now){
		if(val(now) > x){
			s = val(now),now = ls(now);
		}else{
			now = rs(now);
		}
	}
	return s;
}
int main(){
	srand(time(0));
	n = read();
	while(n--){
		opt = read(),x = read();
		if(opt == 1){
			insert(x,rt);
		}else if(opt == 2){
			del(x,rt);
		}else if(opt == 3){
			pe(xrank(x));
		}else if(opt == 4){
			pe(rankx(x));
		}else if(opt == 5){
			pe(pre(x));
		}else{
			pe(nex(x));
		}
	}
	return 0;
}

有意思的是#5:

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

我本地输出(也就是正确输出):

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

但注释掉 srand(time(0)); 并交上去后倒数第二行输出 12……

2024/8/8 08:46
加载中...