报错信息:
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;
}