悬关 CE 求调
  • 板块灌水区
  • 楼主zhangbo1000
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/6 08:09
  • 上次更新2024/1/6 11:33:52
查看原帖
悬关 CE 求调
760291
zhangbo1000楼主2024/1/6 08:09

错误信息:

(.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=&empty;
			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;
}
2024/1/6 08:09
加载中...