主席树（非权值）

本文主要是介绍主席树（非权值），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

int n;
const int N=4e5;
const int LOGN=22;
namespace ST{
    const int M=N*LOGN;
    int son[M][2],ct[M];
    int node_count;
    int new_node(int ls,int rs,int cnt){
        int t=++node_count;
        son[t][0]=ls;
        son[t][1]=rs;
        ct[t]=cnt;
        return t;
    }
    int build(int L=0,int R=n-1){
        if(L==R)return new_node(0,0,0);
        int mm=L+(R-L)/2;
        return new_node(build(L,mm),build(mm+1,R),0);
    }
    int insert(int t,int pos,int v,int L=0,int R=n-1){
        if(L==R)return new_node(0,0,ct[t]+v);
        int mm=L+(R-L)/2;
        if(pos<=mm)return new_node(insert(son[t][0],pos,v,L,mm),son[t][1],ct[t]+v);
        return new_node(son[t][0],insert(son[t][1],pos,v,mm+1,R),ct[t]+v);
    }
    int count(int t,int l,int r,int L=0,int R=n-1){
        if(l==L&&r==R)return ct[t];
        int mm=L+(R-L)/2;
        if(r<=mm)return count(son[t][0],l,r,L,mm);
        if(l>mm)return count(son[t][1],l,r,mm+1,R);
        return count(son[t][0],l,mm,L,mm)+count(son[t][1],mm+1,r,mm+1,R);
    }
}
int root[N];
void solve(){
    n=read();
    root[0]=ST::build();
    for(int i=1;i<=n;i++){
        root[i]=root[i-1];
        while(1)switch(getchar()){
            case '+':{
                int x;
                scanf("%d",&x);
                root[i]=ST::insert(root[i],x,1);
                break;
            }
            case '-':{
                int x;
                scanf("%d",&x);
                root[i]=ST::insert(root[i],x,-1);
                break;
            }
            case '\n':{
                goto out;
                break;
            }
        }
        out:;
    }
    int x=0;
    for(int i=1;i<=n;i++){
        int d;
        scanf("%d",&d);
        x=(x+ST::count(root[d],x,n-1))%n;
    }
    cout<<x<<endl;
}

这篇关于主席树（非权值）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！