OJ题号：BZOJ3524、BZOJ2223、洛谷3567
思路：
维护一颗可持久化权值线段树，记录每次加入数字时，不同数字出现的个数。
对于每一个询问$[l,r]$，同时查询以$r$和$l-1$为根的线段树，每次比较两个节点左右字子树的权值和，如果大于$[l,r]$区间的一半就说明这一子区间可能有答案，递归查询即可。
#include<cstdio>
#include<cctype>
#include<cstring>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=,SZ=;
class FotileTree {
private:
int val[SZ],sz,left[SZ],right[SZ];
int newnode() {
return sz++;
}
public:
FotileTree() {
sz=;
memset(val,,sizeof val);
}
int root[N];
int build(const int b,const int e) {
int new_p=newnode();
if(b==e) return new_p;
int mid=(b+e)>>;
left[new_p]=build(b,mid);
right[new_p]=build(mid+,e);
return new_p;
}
int modify(const int p,const int b,const int e,const int x) {
int new_p=newnode();
val[new_p]=val[p]+;
if(b==e) return new_p;
int mid=(b+e)>>;
if(x<=mid) left[new_p]=modify(left[p],b,mid,x),right[new_p]=right[p];
if(x>mid) right[new_p]=modify(right[p],mid+,e,x),left[new_p]=left[p];
return new_p;
}
int query(const int p1,const int p2,const int b,const int e,const int k) {
if(b==e) return b;
int mid=(b+e)>>;
if(val[left[p2]]-val[left[p1]]>k) return query(left[p1],left[p2],b,mid,k);
if(val[right[p2]]-val[right[p1]]>k) return query(right[p1],right[p2],mid+,e,k);
return ;
}
};
FotileTree t;
int main() {
int n=getint(),m=getint();
t.root[]=t.build(,n);
for(int i=;i<=n;i++) t.root[i]=t.modify(t.root[i-],,n,getint());
while(m--) {
int l=getint(),r=getint();
printf("%d\n",t.query(t.root[l-],t.root[r],,n,(r-l+)>>));
}
return ;
}