AVL树求条

#include<iostream>
#include<cmath>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;

const int MAXL=1e6+5;
int tot,rt;
struct node{
	int l,r,v;
    int cnt,sz,bf,h;
}tr[MAXL];

int newnode(int v){
    tr[++tot].v=v;
    tr[tot].cnt=tr[tot].sz=tr[tot].h=1;
    return tot;
}
void recover(int x){
    int l=tr[x].l,r=tr[x].r;
    tr[x].sz=tr[l].sz+tr[r].sz+tr[x].cnt;
    tr[x].h=max(tr[tr[x].l].h,tr[tr[x].r].h)+1;
    tr[x].bf=tr[tr[x].l].h-tr[tr[x].r].h;
}
void build(){
	newnode(-inf),newnode(inf);
	rt=1,tr[1].r=2;
    recover(rt);
}
void rrotate(int &x){
    int y=tr[x].l;
    tr[x].l=tr[y].r;
    tr[y].r=x,x=y;
    recover(tr[x].r);
    recover(x);
}
void lrotate(int &x){
    int y=tr[x].r;
    tr[x].r=tr[y].l;
    tr[y].l=x;
    x=y;
    recover(tr[x].l);
    recover(x);
}
void maintain(int &x){
    recover(x);
    int l=tr[x].l,r=tr[x].r;
    int bf=tr[x].bf;
    if(bf==2){
        if(tr[tr[l].l].h>=tr[tr[r].l].h)rrotate(x);
        else lrotate(l),rrotate(x);
    }
    else if(bf==-2){
        if(tr[tr[l].r].h<=tr[tr[r].r].h)lrotate(x);
        else rrotate(r),lrotate(x);
    }
    recover(x);
}
void insert(int &x,int v){
    if(x==0){
        x=newnode(v);
        return;
    }
    if(v==tr[x].v){
        tr[x].cnt++;
        recover(x);
        return;
    }
    if(tr[x].v>v)insert(tr[x].l,v);
    else insert(tr[x].r,v);
    maintain(x);
}
void remove(int &x,int v){
    if(x==0)return;
    if(v==tr[x].v){
        if(tr[x].cnt>1){
            tr[x].cnt--;
            recover(x);
            return;
        }
        if(tr[x].l&&tr[x].r){
            int nxt=tr[x].r;
            while(tr[nxt].l)nxt=tr[nxt].l;
            tr[x].v=tr[nxt].v;
            remove(tr[x].r,tr[nxt].v);
        }
        else if(tr[x].l)x=tr[x].l;
        else if(tr[x].r)x=tr[x].r;
        else x=0;
    }
    else if(tr[x].v>v)remove(tr[x].l,v);
    else remove(tr[x].r,v);
    maintain(x);
}
int getnext(int v){
	int x=rt,ans=2;
	while(x){
		if(tr[x].v==v){
			if(tr[x].r){
				x=tr[x].r;
				while(tr[x].l)x=tr[x].l;
				return x;
			}
			break;
		}
		if(tr[x].v>v&&tr[x].v<tr[ans].v)ans=x;
		if(tr[x].v>v)x=tr[x].l;
		else x=tr[x].r;
	}
	return ans;
}
int getpre(int v){
	int x=rt,ans=1;
	while(x){
		if(tr[x].v==v){
			if(tr[x].l){
				x=tr[x].l;
				while(tr[x].r)x=tr[x].r;
				return x;
			}
			break;
		}
		if(tr[x].v<v&&tr[x].v>tr[ans].v)ans=x;
		if(tr[x].v>v)x=tr[x].l;
		else x=tr[x].r;
	}
	return ans;
} 
int getrnk(int x,int v){
    if(x==0)return 1;
    if(v==tr[x].v)return tr[tr[x].l].sz+1;
    if(v<tr[x].v)return getrnk(tr[x].l,v);
    return getrnk(tr[x].r,v)+tr[tr[x].l].sz+tr[x].cnt;
}
int getkth(int x,int k){
    if(k>tr[x].sz)return 2;
    if(k<=tr[tr[x].l].sz)return getkth(tr[x].l,k);
    if(k<=tr[tr[x].l].sz+tr[x].cnt)return x;
    return getkth(tr[x].r,k-tr[tr[x].l].sz-tr[x].cnt);
}