题解：
要求出现次数大于（R-L+1）/2的数，这样的数最多只有一个。我们对序列做主席树，每个节点记录出现的次数和（sum）。（这里忽略版本差值问题）对于一个节点，如果左儿子的sum小于等于（R-L+1）/2，则答案不可能在左儿子中；右儿子同理。然后对有可能的儿子递归寻找答案，如果左右儿子都不可能，则不存在答案。
代码：
BZOJ 3524：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(5e5)+,maxm=maxn;
int N,M,L,R,root[maxn],num_treenode=,A;
struct Tree{
int l,r,sum,ls,rs;
}t[(maxn<<)+maxn*];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r)return;
Build(t[x].ls=++num_treenode,l,mid);Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline void Update(int u,int x,int q){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
t[x].l=l;t[x].r=r;
if(l==r&&l==q){
t[x].sum=t[u].sum+;
return;
}
if(q<=mid){
t[x].rs=t[u].rs;
Update(t[u].ls,t[x].ls=++num_treenode,q);
}
else {
t[x].ls=t[u].ls;
Update(t[u].rs,t[x].rs=++num_treenode,q);
}
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
return;
}
inline int Query(int u,int x,int z){
int l=t[u].l,r=t[u].r;
if(l==r)return l;
if(t[t[x].ls].sum-t[t[u].ls].sum>z)return Query(t[u].ls,t[x].ls,z);
if(t[t[x].rs].sum-t[t[u].rs].sum>z)return Query(t[u].rs,t[x].rs,z);
return ;
}
int main(){
N=rd();M=rd();
Build(root[]=++num_treenode,,N);
for(int i=;i<=N;i++){
A=rd();
Update(root[i-],root[i]=++num_treenode,A);
}
while(M--){
L=rd();R=rd();
printf("%d\n",Query(root[L-],root[R],(R-L+)>>));
}
return ;
}
BZOJ 2223：
这道题的样例很坑，我整理了一下：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(3e5)+,maxm=;
int N,M,L,R,root[maxn],num_treenode=,A,ans,Lim;
struct Tree{
int l,r,sum,ls,rs;
}t[(maxn<<)+maxn*];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r)return;
Build(t[x].ls=++num_treenode,l,mid);Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline void Update(int u,int x,int q){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
t[x].l=l;t[x].r=r;
if(l==r&&l==q){
t[x].sum=t[u].sum+;
return;
}
if(q<=mid){
t[x].rs=t[u].rs;
Update(t[u].ls,t[x].ls=++num_treenode,q);
}
else {
t[x].ls=t[u].ls;
Update(t[u].rs,t[x].rs=++num_treenode,q);
}
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
return;
}
inline int Query(int u,int x,int z){
int l=t[u].l,r=t[u].r;
if(l==r)return l;
if(t[t[x].ls].sum-t[t[u].ls].sum>z)return Query(t[u].ls,t[x].ls,z);
if(t[t[x].rs].sum-t[t[u].rs].sum>z)return Query(t[u].rs,t[x].rs,z);
return ;
}
int main(){
N=rd();Lim=rd();
Build(root[]=++num_treenode,,Lim);
for(int i=;i<=N;i++){
A=rd();
Update(root[i-],root[i]=++num_treenode,A);
}
M=rd();
while(M--){
L=rd();R=rd();
if(L>R){
printf("no\n");
continue;
}
ans=Query(root[L-],root[R],(R-L+)>>);
if(ans==)printf("no\n");else printf("yes %d\n",ans);
}
return ;
}
By:AlenaNuna