T122936 区间主元素问题题解

看过前面几位 $dalao$ 们的题解的一定都知道了这个： $\huge\texttt{“}$ $$\texttt{如果存在主元素，则主元素一定是中位数。”}$$ 那么本题就可以通过这个性质进行求解。 那么本题就可以转化为： $$\texttt{给定一个序列，求他的中位数，并判定这个数出现次数是否大于区间长度的一半。}$$ 可能有人已经激动起来了。 没错，就是： $$\color{red}\huge\texttt{主席树}$$ 这里摆上主席树的板子，如果不了解的可以左转 [这里](https://www.luogu.com.cn/problem/T122936)。 $Code:$ ```cpp class chairmanTree { // Private section public: void build(int a[],int n){ for(int i=1;i<=n;i++)b[i]=a[i]; sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; rt[0]=_build(1,m); for(int i=1;i<=n;i++)rt[i]=add(rt[i-1],lower_bound(b+1,b+m+1,a[i])-b,1,m); } int query(int l,int r,int k){ return b[_query(rt[l-1],rt[r],1,m,k)]; } // Public Declarations protected: int m; int tot; int b[maxn]; int rt[maxn]; int lc[maxn<<5]; int rc[maxn<<5]; int su[maxn<<5]; int _build(int l,int r){ int now=++tot,mid=(l+r)>>1; su[now]=0; if(l<r)lc[now]=_build(l,mid),rc[now]=_build(mid+1,r); return now; } int add(int last,int num,int l,int r){ int now=++tot,mid=(l+r)>>1; lc[now]=lc[last],rc[now]=rc[last],su[now]=su[last]+1; if(l<r){ if(num<=mid)lc[now]=add(lc[last],num,l,mid); else rc[now]=add(rc[last],num,mid+1,r); } return now; } int _query(int last1,int last2,int l,int r,int k){ if(l>=r)return l; int num=su[lc[last2]]-su[lc[last1]],mid=(l+r)>>1; if(num>=k)return _query(lc[last1],lc[last2],l,mid,k); return _query(rc[last1],rc[last2],mid+1,r,k-num); } // Protected Declarations }; ``` 最后只需要稍微改一点就好啦！