[文章目录]
Description
给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。n,m≤500000
区间一个数出现次数大于(r-l+1)/2的数只能有一个（废话！！！）
所以说，如果一个区间存在合法解的话，所以，如果将权值按照区间划分的话，如果一个区间内的个数<(r-l+1)/2的话，这个区间就没有用了。
维护主席树，然后每次只会进入一个儿子，如果没有就直接跳出，直到找到一个儿子。
2534:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,c[501000],b[501000],w[501000],tot,cnt;
int getid(int x)
{
int l=1,r=tot+1,mid;
while(l<r)
{
mid=l+r>>1;
if(x<=c[mid]) r=mid;
else l=mid+1;
}
return r;
}
int root[501000];
struct seg
{
int ls,rs,siz;
}t[10001000];
void update(int l,int r,int &x,int y,int z)
{
x=++cnt; t[x].siz=t[y].siz+1;
if(l==r) return ;
int mid=l+r>>1;
if(z<=mid) t[x].rs=t[y].rs,update(l,mid,t[x].ls,t[y].ls,z);
else t[x].ls=t[y].ls,update(mid+1,r,t[x].rs,t[y].rs,z);
}
int query(int l,int r,int x,int y,int z)
{
if(l==r) return l;
if(t[t[y].ls].siz-t[t[x].ls].siz>z) return query(l,l+r>>1,t[x].ls,t[y].ls,z);
if(t[t[y].rs].siz-t[t[x].rs].siz>z) return query((l+r>>1)+1,r,t[x].rs,t[y].rs,z);
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&w[i]),b[i]=w[i];
sort(b+1,b+n+1); c[++tot]=b[1];
for(int i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(int i=1;i<=n;++i)
update(1,tot,root[i],root[i-1],getid(w[i]));
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",c[query(1,tot,root[x-1],root[y],(y-x+1)/2)]);
}
return 0;
}