浅谈主席树：https://www.cnblogs.com/AKMer/p/9956734.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3524
假设数列不是一开始就给你的，而是一次一次修改操作让你插入数值xx，而询问是问你从第L次插入到第R次操作间，有没有哪个数值插入次数超过(R−L+1)/2，把题意这么一转化，就很好用主席树写了。
我们可以在值域上建立主席树，每个结点统计值域在[l,r]内的数字有多少个。那么只需要用第r个版本的主席树的cnt减去第l−1个版本的主席树的cnt，就是操作[L,R]里插入了多少次值域在[l,r]的数字。如果[l,mid]的次数大于(R−L+1)/2那么答案就在[l,mid]，同理可以去判断答案是否在[mid+1,r]内，如果都不满足，那么就不存在这样的数值，直接返回0就行了。
时间复杂度：O((n+m)logn)
空间复杂度：O(nlogn)
#include <cstdio>
using namespace std;
const int maxn=5e5+5;
int n,m;
int rt[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<‘0‘||ch>‘9‘;ch=getchar())if(ch==‘-‘)f=-1;
for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())x=x*10+ch-‘0‘;
return x*f;
}
struct tree_node
{
int cnt,ls,rs;
};
struct Chairman_tree
{
int tot;
tree_node tree[maxn*20];
void ins(int lst,int &now,int l,int r,int pos)
{
now=++tot;
tree[now]=tree[lst];
tree[now].cnt++;//先把左右儿子信息全部继承下来，然后区间内数字个数加一
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)
ins(tree[lst].ls,tree[now].ls,l,mid,pos);//新建左儿子
else
ins(tree[lst].rs,tree[now].rs,mid+1,r,pos);//新建右儿子
}
int query(int L,int R,int l,int r,int limit)
{
if(l==r)
{
if(tree[R].cnt-tree[L].cnt>limit)return l;//记得判断
else return 0;
}
int mid=(l+r)>>1;
int tmp1=tree[tree[R].ls].cnt-tree[tree[L].ls].cnt;
int tmp2=tree[tree[R].rs].cnt-tree[tree[L].rs].cnt;
if(tmp1>limit)return query(tree[L].ls,tree[R].ls,l,mid,limit);
if(tmp2>limit)return query(tree[L].rs,tree[R].rs,mid+1,r,limit);
return 0;//同题解所述
}
}T;
int main() {
n=read(),m=read();
for(int i=1;i<=n;i++)
{
int x=read();
T.ins(rt[i-1],rt[i],1,n,x);
//rt[i]表示第i个版本的主席树
}
for(int i=1;i<=m;i++)
{
int l=read(),r=read(),limit=(r-l+1)>>1;
int ans=T.query(rt[l-1],rt[r],1,n,limit);
printf("%d\n",ans);
}
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/11804284.html