蒟蒻不会Splay只能写Treap:
#include<cstdio>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+50;
struct Treap{
int val;
int tot;
int pri;
int size;
int left;
int right;
}a[N];
int n;
int cnt;
int root;
void Pushup(int x)
{
a[x].size=a[a[x].left].size+a[a[x].right].size+a[x].tot;
}
void R_rotate(int &x)
{
int l=a[x].left;
a[x].left=a[l].right;
a[l].right=x;
x=l;
Pushup(a[x].left);
Pushup(x);
}
void L_rotate(int &x)
{
int r=a[x].right;
a[x].right=a[r].left;
a[r].left=x;
x=r;
Pushup(a[x].right);
Pushup(x);
}
void Erase(int &x,int p)
{
if(!x) return ;
if(p==a[x].val)
{
if(a[x].tot>1) a[x].tot--;
else
{
if(!a[x].left||!a[x].right) x=a[x].left+a[x].right;
else if(a[a[x].left].pri<a[a[x].right].pri) R_rotate(x),Erase(x,p);
else L_rotate(x),Erase(x,p);
}
}
if(p<a[x].val) Erase(a[x].left,p);
if(p>a[x].val) Erase(a[x].right,p);
Pushup(x);
}
void Insert(int &x,int p)
{
if(!x)
{
x=++cnt;
a[x].val=p;
a[x].pri=rand();
a[x].size=1;
a[x].tot++;
return ;
}
if(p<a[x].val)
{
Insert(a[x].left,p);
if(a[a[x].left].pri>a[x].pri) R_rotate(x);
}
if(p>a[x].val)
{
Insert(a[x].right,p);
if(a[a[x].right].pri>a[x].pri) L_rotate(x);
}
if(p==a[x].val) a[x].tot++;
Pushup(x);
}
int Find_kth(int x,int p)
{
while(x)
{
if(p==a[a[x].left].size+1) return a[x].val;
if(p<a[a[x].left].size+1) x=a[x].left;
if(p>a[a[x].left].size+1) p-=a[a[x].left].size+1,x=a[x].right;
}
}
int Find_rank(int x,int p)
{
if(!x) return 0;
if(p==a[x].val) return a[a[x].left].size+1;
if(p<a[x].val) return Find_rank(a[x].left,p);
if(p>a[x].val) return a[a[x].left].size+1+Find_rank(a[x].right,p);
}
int Query_pre(int x,int p)
{
int pre=-0x7f7f7f;
while(x)
{
if(p<a[x].val) x=a[x].left;
else pre=a[x].val,x=a[x].right;
}
return pre;
}
int Query_suf(int x,int p)
{
int suf=0x7f7f7f;
while(x)
{
if(p>a[x].val) x=a[x].right;
else suf=a[x].val,x=a[x].left;
}
return suf;
}
int main()
{
scanf("%d",&n);
int opt,x;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&opt,&x);
if(opt==1) Insert(root,x);
if(opt==2) Erase(root,x);
if(opt==3) printf("%d\n",Find_rank(root,x));
if(opt==4) printf("%d\n",Find_kth(root,x));
if(opt==5) printf("%d\n",Query_pre(root,x));
if(opt==6) printf("%d\n",Query_suf(root,x));
}
return 0;
}
结果WA 16,然后下载数据:
Input:
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
Output:
964673
964673
1
964673
3
1
1
964673
964673
评测机显示第5行我的程序输出了4,但是我测了好几遍都输出的是3。这是怎么回事呢?我的程序错在哪里呢?