平衡树板子蒯过来,样例过了,题没过?
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
int n,root,cnt;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
struct sm
{
int val;
int size;
int fa,child[2];
int sum;
}tree[maxn];
void pushup(int x){tree[x].size=tree[tree[x].child[0]].size+tree[tree[x].child[1]].size+tree[x].sum;}
void rotate(int x)
{
int father=tree[x].fa;
int grandfather=tree[father].fa;
int k=(x==tree[father].child[1]);//k=0左子树k=1右子树
tree[grandfather].child[tree[grandfather].child[1]==father]=x;
tree[x].fa=grandfather;
tree[father].child[k]=tree[x].child[k^1];
tree[tree[x].child[k^1]].fa=father;
tree[x].child[k^1]=father;
tree[father].fa=x;
pushup(father);
pushup(x);
}
void splay(int x,int goal)
{
while(tree[x].fa!=goal)
{
int father=tree[x].fa;
int grandfather=tree[father].fa;
if(grandfather!=goal)(tree[father].child[0]==x)^(tree[grandfather].child[0]==father)?rotate(x):rotate(father);
rotate(x);
}
if(goal==0)root=x;
}
void insert(int x)
{
int u=root,father=0;
while(u&&tree[u].val!=x)
{
father=u;
u=tree[u].child[x>tree[u].val];
}
if(u)tree[u].sum++;
else
{
u=++cnt;
if(father)
tree[father].child[x>tree[father].val]=u;
tree[u].child[1]=0;
tree[u].child[0]=0;
tree[u].val=x;
tree[u].size=1;
tree[u].sum=1;
tree[u].fa=father;
}
splay(u,0);
}
void find(int x)
{
int u=root;
if(!u)return;
while(tree[u].child[x>tree[u].val]&&tree[u].val!=x)
u=tree[u].child[x>tree[u].val];
// if(tree[u].val!=x)find(-2147483647);
splay(u,0);
}
int next(int x,int f)//前驱f=0后继=1
{
find(x);
int u=root;
if(tree[u].val>x&&f)return u;
if(tree[u].val<x&&!f)return u;
u=tree[u].child[f];
while(tree[u].child[f^1])u=tree[u].child[f^1];
return u;
}
void delate(int x)
{
int q=next(x,0);
int h=next(x,1);
splay(q,0);
splay(h,q);
int goal=tree[h].child[0];
if(tree[goal].sum>1)
{
tree[goal].sum--;
splay(goal,0);
}
else
tree[h].child[0]=0;
}
int query(int x)
{
int u=root;
if(tree[u].size<x)return 0;
while(1)
{
// cout<<1<<" ";
int l=tree[u].child[0];
if(x>tree[l].size+tree[u].sum)
{
x-=tree[l].size+tree[u].sum;
u=tree[u].child[1];
}
else if(tree[l].size>=x)u=l;
else return tree[u].val;
}
//return tree[u].val;
}
int main()
{
//scanf("%d",&n);
// freopen("ll.in","r",stdin);
// freopen("ll.out","w",stdout);
n=read();
insert(+2147483647);
insert(-2147483647);
for(int i=1;i<=n;i++)
{
//scanf("%d%d",&opt,&x);
int opt=read();
int x=read();
if(opt==5)
{
insert(x);
}
if(opt==1)
{
find(x);
printf("%d\n",tree[tree[root].child[0]].size);
}
if(opt==2)
{
printf("%d\n",query(x+1));
}
if(opt==3)
{
printf("%d\n",tree[next(x,0)].val);
}
if(opt==4)
{
printf("%d\n",tree[next(x,1)].val);
}
}
return 0;
}