【可持久化字段树】HDU - 6191 - Query on A Tree

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db eps=1e-7;
const int N=1e5+7;
int n,q;
int ch[N*40][2],sum[N*40][2],tot;
int rt[N];
void upd(int y,int &x,int pos,int v){
    if(pos<0) return;
    x=++tot;
    int tmp=((v>>pos)&1);
    sum[x][tmp]=sum[y][tmp]+1;
    sum[x][tmp^1]=sum[y][tmp^1];
    ch[x][tmp^1]=ch[y][tmp^1];
    upd(ch[y][tmp],ch[x][tmp],pos-1,v);
}
int que(int x,int y,int pos,int v){
    if(pos<0) return 0;
    int tmp=((v>>pos)&1);
    //关键写法 sum[y][tmp^1]-sum[x][tmp^1]>0表示在y~x版本tire里面 能找到对应值 
    if(sum[y][tmp^1]-sum[x][tmp^1]) return (1<<pos)+que(ch[x][tmp^1],ch[y][tmp^1],pos-1,v);
    else return que(ch[x][tmp],ch[y][tmp],pos-1,v);
}
struct Edge{
    int v,nxt;
}e[N];
int p[N],edn;
void add(int u,int v){
    e[++edn]=(Edge){v,p[u]};p[u]=edn;
}
int val[N];
int le[N],ri[N];
int px[N],tp;
void dfs(int u){
    px[++tp]=u;
    le[u]=tp;
    for(int i=p[u];~i;i=e[i].nxt){
        int v=e[i].v;
        dfs(v);
    }
    ri[u]=tp;
}

int main()
{
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&val[i]);
            p[i]=-1;
        }
        edn=-1;
        for(int i=2,x;i<=n;i++){
            scanf("%d",&x);
            add(x,i);
        }
        tp=0;
        dfs(1);
        tot=0;
        for(int i=1;i<=n;i++){
            int u=px[i];
            upd(rt[i-1],rt[i],30,val[u]);
        }
        for(int i=1,u,x;i<=q;i++){
            scanf("%d%d",&u,&x);
            printf("%d\n",que(rt[le[u]-1],rt[ri[u]],30,x));
        }
    }
} 

CCPC2018-湖南全国邀请赛 HDU6278 Just h-index【主席树+二分查找】

 #include<iostream>
#include<algorithm>
using namespace std;
const int N=100100;
int a[N],b[N],rt[20*N],ls[20*N],rs[20*N],sum[20*N]; 
int id;
void build(int &o,int l,int r){
    o=++id;
    sum[o]=0;
    if(l==r) return;
    int m=(l+r)>>1;
    build(ls[o],l,m);
    build(rs[o],m+1,r);
}

void update(int &o,int l,int r,int last,int p{
    o=++id;
    ls[o]=ls[last];
    rs[o]=rs[last];
    sum[o]=sum[last]+1;
    if(l==r) return;
    int m=(l+r)>>1;
    if(p<=m)
      update(ls[o],l,m,ls[last],p);
    else
      update(rs[o],m+1,r,rs[last],p);
}

//查询区间[L+1,R]内大于等于k的个数
int query(int L,int R,int l,int r,int k){
    if(b[l]>=k) return sum[R]-sum[L];
    if(l==r) return 0;
    int m=(l+r)>>1;
    int sum=0;
    if(b[m]>=k)
      sum+=query(ls[L],ls[R],l,m,k);
    sum+=query(rs[L],rs[R],m+1,r,k);
    return sum; 
} 

int main(){
    int n,q;
    while(~scanf("%d%d",&n,&q)){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        //离散化 
        sort(b+1,b+n+1);
        int size=unique(b+1,b+n+1)-(b+1);
        id=0;
        build(rt[0],1,size);/
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(b+1,b+1+size,a[i])-b;
            update(rt[i],1,size,rt[i-1],a[i]);
        }

        while(q--){
            int L,R;
            scanf("%d%d",&L,&R);
            int l=0,r=R-L+1;
            while(l<=r){//二分查找 
                int m=(l+r)>>1;
                if(query(rt[L-1],rt[R],1,size,m)<m)
                  r=m-1;
                else
                  l=m+1; 
            }
            printf("%d\n",l-1);
        }
    }
}