[求助]写 FHQ Treap编译错误?
  • 板块灌水区
  • 楼主TH911
  • 当前回复17
  • 已保存回复17
  • 发布时间2024/11/21 19:43
  • 上次更新2024/11/21 21:10:54
查看原帖
[求助]写 FHQ Treap编译错误?
967959
TH911楼主2024/11/21 19:43

报错信息:

C:\Users\ADMINI~1\AppData\Local\Temp\ccVaLmWN.o	未命名2.cpp:(.rdata$.refptr._ZN5treap4rootE[.refptr._ZN5treap4rootE]+0x0): undefined reference to `treap::root'
D:\1234\collect2.exe	[Error] ld returned 1 exit status

完整代码:

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<random>
using namespace std;
const int N=1e5;
mt19937 Rand(time(0));
struct treap{
	struct node{
		int value,rand,size;
		int left,right;
	}t[N+1];
	static int root;
	
	void update(int p){
		t[p].size=t[t[p].left].size+t[t[p].right].size+1;
	}
	void split(int p,int x,int &l,int &r){
		if(p==0)l=r=0;
		else{
			if(t[p].value<=x){
				l=p;
				split(t[p].right,x,t[p].right,r);
			}else{
				r=p;
				split(t[p].left,x,l,t[p].left);
			}update(p);
		}
	}
	int merge(int l,int r){
		if(l==0)return r;
		if(r==0)return l;
		if(t[l].rand<t[r].rand){
			t[l].right=merge(t[l].right,r);
			update(l);
			return l;
		}else{
			t[r].left=merge(l,t[r].left);
			update(r);
			return r;
		}
	}
	int create(int x){
		static int top;
		t[++top]={x,(int)Rand(),1,0,0};	
		return top;
	}
	
	void insert(int x){
		int l,r;
		split(root,x,l,r);
		root=merge(merge(l,create(x)),r);
	}
	void remove(int x){
		int l,r,pl;
		split(root,x,l,r);
		split(l,x-1,l,pl);
		pl=merge(t[pl].left,t[pl].right);
		root=merge(merge(l,pl),r);
	}
	int rank(int x){
		int l,r;
		split(root,x-1,l,r);
		int ans=t[l].size+1;
		root=merge(l,r);
		return ans;
	}
	int kth(int k,int p=root){
		if(k<1||k>t[p].size)return 2147483647;
		while(true){
			if(t[t[p].left].size+1==k)break;
			else if(k<t[t[p].left].size+1)p=t[p].left;
			else{
				k-=t[t[p].left].size+1;
				p=t[p].right;
			}
		}return t[p].value;
	}
	int prev(int x){
		int l,r;
		split(root,x-1,l,r);
		int ans=kth(t[l].size,l);
		root=merge(l,r);
		return ans;
	}
	int next(int x){
		int l,r;
		split(root,x,l,r);
		int ans=kth(1,r);
		root=merge(l,r);
		return ans;
	}
}t;
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	int n;
	scanf("%d",&n);
	while(n--){
		int op,x;
		scanf("%d %d",&op,&x);
		switch(op){
			case 1:t.insert(x);break;
			case 2:t.remove(x);break;
			case 3:printf("%d\n",t.rank(x));break;
			case 4:printf("%d\n",t.kth(x));break;
			case 5:printf("%d\n",t.prev(x));break;
			case 6:printf("%d\n",t.next(x));break;
		}
	}
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}
2024/11/21 19:43
加载中...