主席树模板题目

#include
     
      using namespace std;int root[500010],a[500010],hash[500010],dd,n,m,len=0,sum[15000000],l[15000000],r[15000000];int maketree(int L,int R){	int rt=++len;	sum[rt]=0;	if(L
      
       >1;		l[rt]=maketree(L,mid);		r[rt]=maketree(mid+1,R);	}	return rt;}int update(int pre,int L,int R,int x){	int rt=++len;	l[rt]=l[pre];	r[rt]=r[pre];	sum[rt]=sum[pre]+1;	if(L
       
        >1;		if(x<=mid)l[rt]=update(l[pre],L,mid,x);		else r[rt]=update(r[pre],mid+1,R,x);	}	return rt;}int query(int x,int y,int L,int R,int X){	if(L>=R)	{		if(sum[y]-sum[x]>X)return L;		else return 0;	}	int sum1=sum[l[y]]-sum[l[x]],sum2=sum[r[y]]-sum[r[x]];	int mid=(L+R)>>1;	if(sum1>X)return query(l[x],l[y],L,mid,X);	else if(sum2>X)return query(r[x],r[y],mid+1,R,X);	else return 0;}int main(){	//freopen("xf.in","r",stdin);	//freopen("xf.out","w",stdout);	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)	{		scanf("%d",&a[i]);		hash[i]=a[i];	}	sort(hash+1,hash+n+1);	dd=unique(hash+1,hash+n+1)-hash-1;	root[0]=maketree(1,dd);	for(int i=1;i<=n;i++)	{		int x=lower_bound(hash+1,hash+dd+1,a[i])-hash;		root[i]=update(root[i-1],1,dd,x);	}	int x,y;	while(m--)	{		scanf("%d%d",&x,&y);		int ans=query(root[x-1],root[y],1,dd,(y-x+1)/2);		printf("%d\n",hash[ans]);	}	return 0;}
       
      
     

　　

#include
     
      using namespace std;int w,root[500010],a[500010],hash[500010],dd,n,m,len=0,sum[15000000],l[15000000],r[15000000];int maketree(int L,int R){    int rt=++len;    sum[rt]=0;    if(L
      
       >1;        l[rt]=maketree(L,mid);        r[rt]=maketree(mid+1,R);    }    return rt;}int update(int pre,int L,int R,int x){    int rt=++len;    l[rt]=l[pre];    r[rt]=r[pre];    sum[rt]=sum[pre]+1;    if(L
       
        >1;        if(x<=mid)l[rt]=update(l[pre],L,mid,x);        else r[rt]=update(r[pre],mid+1,R,x);    }    return rt;}int query(int x,int y,int L,int R,int X){    if(L>=R)    {        if(sum[y]-sum[x]>X)return L;        else return 0;    }    int sum1=sum[l[y]]-sum[l[x]],sum2=sum[r[y]]-sum[r[x]];    int mid=(L+R)>>1;    if(sum1>X)return query(l[x],l[y],L,mid,X);    else if(sum2>X)return query(r[x],r[y],mid+1,R,X);    else return 0;}int main(){    //freopen("xf.in","r",stdin);    //freopen("xf.out","w",stdout);    scanf("%d%d",&n,&w);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);        hash[i]=a[i];    }    scanf("%d",&m);    sort(hash+1,hash+n+1);    dd=unique(hash+1,hash+n+1)-hash-1;    root[0]=maketree(1,dd);    for(int i=1;i<=n;i++)    {        int x=lower_bound(hash+1,hash+dd+1,a[i])-hash;        root[i]=update(root[i-1],1,dd,x);    }    int x,y;    while(m--)    {        scanf("%d%d",&x,&y);        int ans=query(root[x-1],root[y],1,dd,(y-x+1)/2);        if(ans==0)printf("no\n");        else printf("yes %d\n",hash[ans]);    }    return 0;}