AVL模板

注意左旋右旋方式

LL LR RR RL 的处理方式

右 子左自右 左 子右自左

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
struct node{
	int l, r, val;
	int height, size;
}avl[maxn];
int cnt = 0, root;
inline void add(int &now,int val){
	avl[now = ++ cnt].val = val; 
	avl[cnt].size = 1;
}
inline void update(int now){
	avl[now].size = avl[avl[now].l].size + avl[avl[now].r].size + 1;
	avl[now].height = max(avl[avl[now].l].height, avl[avl[now].r].height)+1;
}


inline int factor(int now){
	return avl[avl[now].l].height - avl[avl[now].r].height;
}

inline void lrotate(int &now){// 左旋
	int r = avl[now].r;
	avl[now].r = avl[r].l;
	avl[r].l = now;
	now = r;
	update(avl[now].l), update(now);
}
inline void rrotate(int &now){// 右旋
	int l = avl[now].l;
	avl[now].l = avl[l].r;
	avl[l].r = now;
	now = l;
	update(avl[now].r),update(now);
}

inline void check(int &now){// 检查是否平衡
	int nf = factor(now);
	if(nf > 1){
		int lf = factor(avl[now].l);
		if(lf > 0) rrotate(now);
		else lrotate(avl[now].l),rrotate(now);
	}
	else if(nf < -1){
		int rf = factor(avl[now].r);
		if(rf < 0) lrotate(now);
		else rrotate(avl[now].r),lrotate(now);
	}
	else if(now) update(now);
}

void ins(int &now, int val){
	if(!now) add(now, val);
	else if(val < avl[now].val) ins(avl[now].l, val);
	else ins(avl[now].r, val);
	check(now);
}

int find(int &now, int fa){
	int ret;
	if(!avl[now].l){
		ret = now;
		avl[fa].l = avl[now].r;
	}
	else {
		ret = find(avl[now].l, now);
		check(now);
	}
	return ret;
}
void del(int &now, int val){
	if(val == avl[now].val){
		int l = avl[now].l, r = avl[now].r;
		if(!l || !r) now = l + r;
		else{
			now = find(r, r);
			if(now != r)
				avl[now].r = r;
			avl[now].l = l;
		}
	}
	else if(val < avl[now].val) del(avl[now].l,val);
	else del(avl[now].r, val);
	check(now);
}
int getrank(int val){
	int now = root, rank = 1;
	while(now){
		if(val <= avl[now].val){
			now = avl[now].l;
		} else{
			rank += avl[avl[now].l].size + 1;
			now = avl[now].r;
		}
	}
	return rank;
}
int getnum(int rank){
	int now = root;
	while(now){
		if(avl[avl[now].l].size + 1 == rank){
			break;
		}
		else if(avl[avl[now].l].size >= rank){
			now = avl[now].l;
		}
		else{
			
			rank -= avl[avl[now].l].size + 1;
			now = avl[now].r;
		}
	}
	return avl[now].val;
}
int main()
{
	int n;
	scanf("%d",&n);
	while(n --){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt == 1)
            ins(root,x);
             
        if(opt == 2)
            del(root,x); 
        if(opt == 3)
            printf("%d\n",getrank(x));
        if(opt == 4)
            printf("%d\n",getnum(x));
        if(opt == 5)
            printf("%d\n",getnum(getrank(x)-1));
        if(opt == 6)
            printf("%d\n",getnum(getrank(x+1)));
         
	}
}