跳跃表学习笔记

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x7f7f7f7f;
const int N = 1e5+10,MAXL = 10;// 若概率为0.5，则改为20
int n,lv,tot[MAXL],sz;//最高层数 当前层到当前点的节点数 节点个数 
typedef struct node{
	int val;//值 
	int di[MAXL];//与下一个节点之间的距离 
	struct node* forward[MAXL];//(链表意义上的)后继指针数组 
}*nodeptr;
nodeptr head,updata[MAXL+1];//头结点 访问路径中每层的最高节点 

void init(){
    srand(time(0));
	lv = 0;
	head = new(node);
	for(int i = 0;i < MAXL;++ i){
		head->forward[i] = NULL;
		head->di[i] = 0;
	}
	head->val = -inf;
	return;
}

inline int randlevel(){
	int lay = 1;
	while((rand()&1) && (rand()&1) && lay < MAXL) 
		++ lay;
	return lay;
}

int find(int val){//小于val的元素个数 
	nodeptr p = head;
	tot[lv] = 0;
	for(int i = lv-1;i >= 0;-- i){
		tot[i] = tot[i+1];
		while(p->forward[i] && p->forward[i]->val < val)
			tot[i] += p->di[i],p = p->forward[i];
		updata[i] = p;
	}
	return tot[0];
}

void insert(int val){//插入元素 
	nodeptr p = new(node);
	find(val);
	p->val = val;
	int lay = randlevel();
	if(lay > lv){
		for(int i = lv;i < lay;++ i){
			updata[i] = head;
            updata[i]->di[i] = sz;
            tot[i] = 0;
		}
			
		lv = lay;
	}
	for(int i = 0;i < lay;++ i){
		p->forward[i] = updata[i]->forward[i];
		p->di[i] = updata[i]->di[i] - (tot[0] - tot[i]);
		updata[i]->forward[i] = p;
		updata[i]->di[i] = tot[0] - tot[i] + 1;
	}
	for(int i = lay;i < lv;++ i)
		++ updata[i]->di[i];
	++ sz; 
	return;
}

void remove(int val){//删除元素 
	find(val);
	nodeptr p = updata[0]->forward[0];
	for(int i = 0;i < lv;++ i){
		if(updata[i]->forward[i] == p){
			updata[i]->di[i] += p->di[i]-1;
			updata[i]->forward[i] = p->forward[i]; 			
		}else -- updata[i]->di[i]; 
	} 
	while(lv && !head->forward[lv-1])
		-- lv; 
	delete(p);
	-- sz; 
	return;
}

int kth(int k){//求第k小数 
	nodeptr p = head;
	for(int i = lv-1;i >= 0;-- i)
		while(p->forward[i] && p->di[i] < k)
			k -= p->di[i],p = p->forward[i];
	return p->forward[0]->val;
}

int rnk(int val){
	nodeptr p = head;
	int res = 0;
	for(int i = lv-1;i >= 0;-- i){
		while(p->forward[i] && p->forward[i]->val < val)
			res += p->di[i],p = p->forward[i];
	}
	return res + 1;
}

nodeptr getpre(int val){//前驱 
	nodeptr p = head;
	for(int i = lv-1;i >= 0;-- i){
		while(p->forward[i] && p->forward[i]->val < val)
			p = p->forward[i];
	}
	return p;
}

nodeptr getnxt(int val){//后继 
	nodeptr p = head;
	for(int i = lv-1;i >= 0;-- i){
		while(p->forward[i] && p->forward[i]->val <= val)
			p = p->forward[i];
	}
	return p->forward[0];
}

int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	cin >> n;
	init();
	while(n --){
		int op,x;
		cin >> op >> x;
		switch(op){
		case 1: insert(x);break;
		case 2: remove(x);break;
		case 3: cout << rnk(x) << '\n';break;
		case 4: cout << kth(x) << '\n';break;
		case 5: cout << getpre(x)->val << '\n';break;
		case 6: cout << getnxt(x)->val << '\n';
		}
	//	cout << "Right";
	//	getchar();
	}
	return 0;
}