应该是1吧.JPG
by Karbet937 @ 2020-04-15 14:01:03
@[Karbet937](/user/339034) 我也觉得是。
而且我从平衡树模板扒拉过来的代码玄学错了。
by 275307894a @ 2020-04-15 14:02:37
@[275307894a](/user/181766) WA么
by Karbet937 @ 2020-04-15 14:03:34
~~我不敢扒拉 我去扒拉我就一辈子上不了蓝了~~
by Karbet937 @ 2020-04-15 14:04:05
是的
by 275307894a @ 2020-04-15 14:04:19
@[275307894a](/user/181766) 我就是贴的平衡树,然后这个的确是1,我的代码也输出1,代码送你吧~:
```cpp
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<cstdio>
using namespace std;
struct node
{
int l,r,v,s,ss;
};
node a[10010];
const int oo=2147483647;
int xx=0,root=0,last=0,ans,t;
inline void update(int p)
{
a[p].ss=a[a[p].l].ss+a[a[p].r].ss+1;
}
void insert(int &p,int vv)
{
if(!p)
{
p=++xx;
a[p].v=vv;
a[p].s=rand();
update(p);
return;
}
if(vv<a[p].v)
{
insert(a[p].l,vv);
if(a[p].s>a[a[p].l].s&&a[a[p].l].s)
{
int b=a[p].l;
a[p].l=a[b].r;
a[b].r=p;
update(p);
p=b;
}
}
else
{
insert(a[p].r,vv);
if(a[p].s>a[a[p].r].s&&a[a[p].r].s)
{
int b=a[p].r;
a[p].r=a[b].l;
a[b].l=p;
update(p);
p=b;
}
}
update(p);
}
void find1(int p,int x)
{
if(!p)
{
return;
}
if(x<=a[p].v)
{
find1(a[p].l,x);
}
else
{
ans+=a[a[p].l].ss+1;
find1(a[p].r,x);
}
}
void find2(int p,int x)
{
if(!p||a[p].ss+t<x)
{
return;
}
if(x<=a[a[p].l].ss+t)
{
find2(a[p].l,x);
}
if(x==t+a[a[p].l].ss+1)
{
ans=a[p].v;
}
if(x>t+a[a[p].l].ss+1)
{
t+=a[a[p].l].ss+1;
find2(a[p].r,x);
}
}
void find3(int p,int x)
{
if(!p)
{
return;
}
if(a[p].v<x)
{
ans=max(ans,a[p].v);
}
if(x<=a[p].v)
{
find3(a[p].l,x);
}
else
{
find3(a[p].r,x);
}
}
void find4(int p,int x)
{
if(!p)
{
return;
}
if(a[p].v>x)
{
ans=min(ans,a[p].v);
}
if(x>=a[p].v)
{
find4(a[p].r,x);
}
else
{
find4(a[p].l,x);
}
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int main()
{
ios::sync_with_stdio(false);
srand(time(0));
int n=read();
for(int i=1;i<=n;i++)
{
int s=read(),x=read();
if(s==1)
{
ans=1;
find1(root,x);
}
if(s==2)
{
ans=0,t=0;
find2(root,x);
}
if(s==3)
{
ans=-oo;
find3(root,x);
}
if(s==4)
{
ans=oo;
find4(root,x);
}
if(s==5)
{
insert(root,x);
}
if(s!=5)
{
cout<<ans<<endl;
}
}
return 0;
}
```
by liqingyang @ 2020-04-15 14:59:58
@[liqingyang](/user/272088) 您这道题过了吗
by 275307894a @ 2020-04-15 15:03:50
我的代码和您的拍不出错
by 275307894a @ 2020-04-15 15:07:49