在代码的第200行(treap类的末尾print函数的唯一一行代码)里面调用了 print(root,0) ,但是这个函数是之前调试的时候用的,忘记删除了,本来还有一个接受两个参数的 print(int,int) 来被调用,在提交的时候只删除了 print(int,int) 函数,但是没有删除调用这个函数的语句,其他的地方也没有 print 函数了。但是这样的代码居然没有编译错误。
所以说为什么这份代码没有在编译的时候报错呢?如果真的调用了 print(int,int) 的话,在运行的时候会发生什么
#include <iostream>
#include <cstdlib>
using namespace std;
const int p=1e5+5;
//树堆
//二叉搜索树+小根堆
template <class type>
class treap
{
private:
template <class node_type>
struct node
{
node_type value;
long long level;
int ls,rs;
int size,num;
};
node<type> t[p];
int cnt,root;
int create(int value)
{
cnt++;
t[cnt].value=value;
t[cnt].level=rand();
t[cnt].size=1;
t[cnt].num=1;
return cnt;
}
//更新节点大小
void update(int id)
{
t[id].size=t[id].num+t[t[id].ls].size+t[t[id].rs].size;
}
//(把)左(子节点)旋(转到上面)
void zig(int &id)
{
int u=t[id].ls;
t[id].ls=t[u].rs;
t[u].rs=id;
update(id);
update(u);
id=u;
}
//(把)右(子节点)旋(转到上面)
void zag(int &id)
{
int u=t[id].rs;
t[id].rs=t[u].ls;
t[u].ls=id;
update(id);
update(u);
id=u;
}
void insert(int &id,type u)
{
if(!id)
{
id=create(u);
return;
}
t[id].size++;
if(t[id].value==u)
{
t[id].num++;
return;
}
if(u<t[id].value)
{
insert(t[id].ls,u);
if(t[t[id].ls].level<t[id].level)
zig(id);
}
else if(t[id].value<u)
{
insert(t[id].rs,u);
if(t[t[id].rs].level<t[id].level)
zag(id);
}
}
void erase(int &id,type u)
{
if(t[id].value==u&&t[id].num>=2)
{
t[id].num--;
t[id].size--;
return;
}
t[id].size--;
if(u<t[id].value)
erase(t[id].ls,u);
else if(t[id].value<u)
erase(t[id].rs,u);
else
{
t[id].size++;
if(t[id].ls==0&&t[id].rs==0)
{
id=0;
return;
}
long long l1=t[t[id].ls].level,l2=t[t[id].rs].level;
if(t[id].ls==0)
l1=1e16;
if(t[id].rs==0)
l2=1e16;
if(l1<l2)
{
zig(id);
t[id].size--;
erase(t[id].rs,u);
}
else
{
zag(id);
t[id].size--;
erase(t[id].ls,u);
}
}
}
int getrank(int id,type u)
{
if(id==0)
return 1;
if(t[id].value==u)
return t[t[id].ls].size+1;
if(u<t[id].value)
return getrank(t[id].ls,u);
if(t[id].value<u)
return t[t[id].ls].size+t[id].num+getrank(t[id].rs,u);
}
type getnum(int id,int rank)
{
if(rank<=t[t[id].ls].size)
return getnum(t[id].ls,rank);
else if(t[t[id].ls].size<rank&&rank<=t[t[id].ls].size+t[id].num)
return t[id].value;
else
return getnum(t[id].rs,rank-t[t[id].ls].size-t[id].num);
}
//小于等于u的最大值
type upper(int id,type u)
{
if(t[id].value==u)
return u;
type ans=-0x3f3f3f3f;
if(u<t[id].value&&t[id].ls!=0)
ans=upper(t[id].ls,u);
else if(t[id].value<u)
{
ans=t[id].value;
if(t[id].value<u&&t[id].rs!=0)
ans=max(ans,upper(t[id].rs,u));
}
return ans;
}
//大于等于u的最小值
type lower(int id,type u)
{
if(t[id].value==u)
return u;
type ans=0x3f3f3f3f;
if(t[id].value<u&&t[id].rs!=0)
ans=lower(t[id].rs,u);
else if(u<t[id].value)
{
ans=t[id].value;
if(u<t[id].value&&t[id].ls!=0)
ans=min(ans,lower(t[id].ls,u));
}
return ans;
}
public:
void insert(type insert_number)
{
insert(root,insert_number);
}
void erase(type erase_number)
{
erase(root,erase_number);
}
int getrank(type number)
{
return getrank(root,number);
}
type getnum(int rank)
{
return getnum(root,rank);
}
type pre(int number)
{
return upper(root,number-1);
}
type next(int number)
{
return lower(root,number+1);
}
void print()
{
print(root,0);
}
};
treap<int> t;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int op,num;
cin>>op>>num;
if(op==1)
t.insert(num);
else if(op==2)
t.erase(num);
else if(op==3)
cout<<t.getrank(num)<<"\n";
else if(op==4)
cout<<t.getnum(num)<<"\n";
else if(op==5)
cout<<t.pre(num)<<"\n";
else if(op==6)
cout<<t.next(num)<<"\n";
}
return 0;
}