我尝试使用 Splay 写这道题,使用 C++20 O2 提交 T 了第四个点。
我把第四个点下载下来发现只有 n=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