错误信息:
(.rdata$.refptr._ZN3BST4node5emptyE[.refptr._ZN3BST4node5emptyE]+0x0): undefined reference to `BST::node::empty'
[错误] ld returned 1 exit status
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<random>
using namespace std;
inline char gtc(){
static char tmp[1000000],*p=0,*top=0;
if(p==top){
p=tmp;
top=tmp+fread(tmp,1,1000000,stdin);
}
return *p++;
}
#define getchar() gtc()
inline void read(int& x){
static char c;
while((c=getchar())<'0');
x=c^'0';
while((c=getchar())>='0')x=(x<<1)+(x<<3)+(c^'0');
}
namespace BST{
mt19937 rng;
class node{
typedef node* bst;
private:
bst ls,rs;
int val,wgt,size,cnt;
static const int none = -1000000000;
public:
static node empty;
node(){
ls=rs=∅
val=none;
size=0;
wgt=rng();
}
void left(bst&);
void right(bst&);
void ins(bst&,const int&);
void del(bst&,const int&);
int search(bst&,const int&);
int search_rank(bst&,const int&);
int pre(const bst&,const int&);
int next(const bst&,const int&);
private:
void zhongxu(const bst& x){
if(x==&empty)return;
zhongxu(x->ls);
for(int i=1;i<=x->cnt;i++)cout<<x->val<<' ';
zhongxu(x->rs);
}
inline void update(){
size=rs->size+ls->size+cnt;
}
};
void node::right(bst& x){
static bst rs;
rs=x->rs;
x->rs=rs->ls;
rs->ls=x;
rs->size=x->size;
x->update();
x=rs;
}
void node::left(bst& x){
static bst ls;
ls=x->ls;
x->ls=ls->rs;
ls->rs=x;
ls->size=x->size;
x->update();
x=ls;
}
void node::ins(bst& tree,const int& x){
if(tree==&empty)tree=new node;
if(tree->val==x){
tree->size++;
tree->cnt++;
return;
}
if(tree->val==none){
tree->size=1;
tree->cnt=1;
tree->val=x;
return;
}
if(x<tree->val){
ins(tree->ls,x);
if(tree->ls->wgt<tree->wgt)left(tree);
}
else {
ins(tree->rs,x);
if(tree->rs->wgt<tree->wgt)right(tree);
}
tree->update();
}
void node::del(bst& tree,const int& x){
if(tree->val==x){
if(tree->cnt>1){
tree->cnt--;
tree->size--;
return;
}
if(tree->ls==&empty||tree->rs==&empty){
tree=(tree->ls==&empty?tree->rs:tree->ls);
return;
}
if(tree->ls->wgt<tree->rs->wgt)right(tree),del(tree->ls,x);
else left(tree),del(tree->rs,x);
tree->update();
return;
}
if(x<tree->val){
del(tree->ls,x);
tree->update();
}
else del(tree->rs,x),tree->update();
}
int node::search(bst& tree,const int& x){
if(tree==&empty)return 0;
if(x==tree->val)return tree->ls->size;
if(x<tree->val)return search(tree->ls,x);
return search(tree->rs,x)+tree->ls->size+tree->cnt;
}
int node::search_rank(bst& tree,const int& x){
if(tree->ls==&empty&&tree->rs==&empty)return tree->val;
if(tree->ls->size<x&&tree->ls->size+tree->cnt>=x)return tree->val;
if(tree->ls->size>=x)return search_rank(tree->ls,x);
return search_rank(tree->rs,x-tree->ls->size-tree->cnt);
}
int node::pre(const bst& tree,const int& x){
static bst p;
static int ans;
p=tree;
ans=0x80000000;
while(p!=&empty){
if(p->val<x)ans=p->val,p=p->rs;
else p=p->ls;
}
return ans;
}
int node::next(const bst& tree,const int& x){
static bst p;
static int ans;
p=tree;
ans=0x7fffffff;
while(p!=&empty){
if(p->val>x)ans=p->val,p=p->ls;
else p=p->rs;
}
return ans;
}
class treap{
friend node;
node* a;
public:
inline void ins(const int& x){a->ins(a,x);}
inline void del(const int& x){a->del(a,x);}
inline int search(const int& x){return a->search(a,x)+1;}
inline int search_rank(const int& x){return a->search_rank(a,x);}
inline int pre(const int& x){return a->pre(a,x);}
inline int next(const int& x){return a->next(a,x);}
};
}
using namespace BST;
treap a;
int main(){
int n,m,last=0,op,x,ans=0;
read(n);
read(m);
for(int i=0;i<n;i++){
read(x);
a.ins(x);
}
while(m--){
read(op);
read(x);
x^=last;
switch (op){
case 1:
a.ins(x);
break;
case 2:
a.del(x);
break;
case 3:
last=a.search(x);
ans^=last;
break;
case 4:
last=a.search_rank(x);
ans^=last;
break;
case 5:
last=a.pre(x);
ans^=last;
break;
default:
last=a.next(x);
ans^=last;
}
}
cout<<ans;
return 0;
}