线段树打平衡树

· · 个人记录

你们看看你们配嘛

普通平衡树

线段树永远的神

维护一个权值线段树

不用离散化，数据范围够小

插入就直接插入

删除就插入-1

查找序号就查找他前面所有值的siz（大小）

找前趋就先把这个数的序号找出来，然后找前面的数

找后趋有点麻烦，需要把这个数一共有几个找到，然后用这个数的序号加上他，再寻找

就这样

看代码

#include<bits/stdc++.h>
using namespace std;
#define re register int 
#define lc x<<1
#define rc x<<1|1
const int N=100005; 
int n;
int siz[N*805];
void update(int x,int l,int r,int pos,int k){
  //插入权值
    if(l==r){
        siz[x]+=k;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid)update(lc,l,mid,pos,k);
    else update(rc,mid+1,r,pos,k);
    siz[x]=siz[lc]+siz[rc];
}
int queryx(int x,int l,int r,int pos,int &sum){
    //找此权值所在的序号，sum是这个权值一共有几个
     if(l==r){
        sum=siz[x];
        return 1;
    }
    int mid=l+r>>1;
    if(pos<=mid)return queryx(lc,l,mid,pos,sum);
    else return siz[lc]+queryx(rc,mid+1,r,pos,sum);
}
int queryp(int x,int l,int r,int xu){
    //找序号为xu的数
    if(l==r)return l;
    int mid=l+r>>1;
    if(siz[lc]>=xu)return queryp(lc,l,mid,xu);
    else return queryp(rc,mid+1,r,xu-siz[lc]);
}
int main(){
    scanf("%d",&n);
    int u;
    int typ[N],x[N],maxn=0,minn=1;
    for(re i=1;i<=n;i++){
        scanf("%d%d",&typ[i],&x[i]);
        if(typ[i]==4)continue;
        maxn=max(maxn,x[i]);
        minn=min(minn,x[i]);
    }
    for(re i=1;i<=n;i++){
        if(typ[i]==1)update(1,minn,maxn,x[i],1);
        if(typ[i]==2)update(1,minn,maxn,x[i],-1);
        if(typ[i]==3)printf("%d\n",queryx(1,minn,maxn,x[i],u));
        if(typ[i]==4)printf("%d\n",queryp(1,minn,maxn,x[i]));
        if(typ[i]==5){
            int o=queryx(1,minn,maxn,x[i],u);
            printf("%d\n",queryp(1,minn,maxn,o-1));
        }
        if(typ[i]==6){
            int o=queryx(1,minn,maxn,x[i],u);
            printf("%d\n",queryp(1,minn,maxn,o+u));
        }
    }
}