神秘现象求助
查看原帖
神秘现象求助
578628
Undead2008楼主2024/7/17 19:25

我尝试使用 Splay 写这道题,使用 C++20 O2 提交 T 了第四个点。

我把第四个点下载下来发现只有 n=20n=20,拿洛谷 IDE 测了一下发现能跑出来,但是交上去死活过不去。

请问这是什么情况(附代码和第四个点的数据)

#include"bits/stdc++.h"
using namespace std;
const int maxn = 100010;
const int Inf = INT_MAX;
struct Node{
	int s[2],p;
	int v,Sz,Szu;
}Tr[maxn];
int TIdx,rt;
inline void MSn(int x,int y,int o){
	Tr[x].s[o]=y,Tr[y].p=x;
}
inline void P(int x){
	Tr[x].Szu=Tr[Tr[x].s[0]].Szu+Tr[x].Sz+Tr[Tr[x].s[1]].Szu;
}
void Ro(int x){
	int y=Tr[x].p,z=Tr[y].p,k=Tr[y].s[1]==x;
	MSn(z,x,Tr[z].s[1]==y),MSn(y,Tr[x].s[k^1],k),MSn(x,y,k^1);
	P(y),P(x);
}
void Splay(int x,int o=0){
	while(Tr[x].p^o){
		int y=Tr[x].p,z=Tr[y].p;
		if(z^o){
			if((Tr[y].s[1]==x)^(Tr[z].s[1]==y))Ro(x);
			else Ro(y);
		}
		Ro(x);
	}
	if(!o)rt=x;
}
void Insert(int v){
	int x=rt,p=0;
	while(x&&Tr[x].v!=v)p=x,x=Tr[x].s[Tr[x].v<v];
	if(!x)x=++TIdx,Tr[x].v=v,Tr[x].p=p,Tr[p].s[Tr[p].v<v]=x;
	Tr[x].Sz++,P(x),Splay(x);
}
int Find_r(int v){
	int x=rt,r=0;
	while(x){
		if(Tr[x].v>v)x=Tr[x].s[0];
		else if(Tr[x].v==v)r+=Tr[Tr[x].s[0]].Szu,Splay(x),x=0;
		else r+=Tr[x].Sz+Tr[Tr[x].s[0]].Szu,x=Tr[x].s[1];
	}
	return r;
}
int Find_k(int k){
	int x=rt,p=0;
	while(x){
		if(Tr[Tr[x].s[0]].Szu>=k)x=Tr[x].s[0];
		else if(Tr[Tr[x].s[0]].Szu+Tr[x].Sz>=k)p=Tr[x].v,Splay(x),x=0;
		else k-=Tr[Tr[x].s[0]].Szu+Tr[x].Sz,x=Tr[x].s[1];
	}
	return p;
}
int FPr(int v){
	int x=rt,p=0,Ans=-Inf;
	while(x){
		if(Tr[x].v<v)Ans=max(Ans,Tr[x].v),p=x,x=Tr[x].s[1];
		else p=x,x=Tr[x].s[0];
	}
	return Splay(p),Ans;
}
int FNe(int v){
	int x=rt,p=0,Ans=Inf;
	while(x){
		if(Tr[x].v>v)Ans=min(Ans,Tr[x].v),p=x,x=Tr[x].s[0];
		else p=x,x=Tr[x].s[1];
	}
	return Splay(p),Ans;
}
int Ps;
int Dl(int x,int y){
	assert(Tr[x].v<Tr[y].v);
	if(!Tr[x].s[1])return MSn(x,y,1),P(x),Ps=x;
	if(!Tr[y].s[0])return MSn(y,x,0),P(y),Ps=y;
	return MSn(x,Dl(Tr[x].s[1],Tr[y].s[0]),1),P(x),MSn(y,x,0),P(y),y;
}
void Delete(int v){
	int x=rt;
	while(Tr[x].v!=v)x=Tr[x].s[Tr[x].v<v];
	Ps=0,Splay(x);
	if(Tr[x].Sz>1)Tr[x].Sz--,P(x);
	else if(Tr[x].s[0]==0||Tr[x].s[1]==0)
		rt=Tr[x].s[0]|Tr[x].s[1],Tr[rt].p=0;
	else rt=Dl(Tr[x].s[0],Tr[x].s[1]),Tr[rt].p=0;
}
int m;
int main(){
	cin>>m;
	Insert(-Inf),Insert(Inf);
	for(int i=1,Ty,x;i<=m;i++){
		cin>>Ty>>x;
		if(Ty==1)Insert(x);
		else if(Ty==2)Delete(x);
		else if(Ty==3)cout<<Find_r(x)<<'\n';
		else if(Ty==4)cout<<Find_k(x+1)<<'\n';
		else if(Ty==5)cout<<FPr(x)<<'\n';
		else cout<<FNe(x)<<'\n';
	}
}
20
1 964673
5 968705
4 1
3 964673
5 965257
1 915269
1 53283
3 964673
3 53283
3 53283
1 162641
5 973984
1 948119
2 915269
2 53283
6 959161
1 531821
1 967521
2 531821
1 343410

2024/7/17 19:25
加载中...