1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll int
using namespace std;
const ll N=5e5;
ll n,m,l,r,lim,tot;
ll a[N+5],rt[N+5];
struct sgt{
ll l,r,cnt;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define cnt(x) tree[x].cnt
}tree[N*25+5];
inline ll build(ll l,ll r) {
ll p=++tot;
if(l==r) return p;
ll mid=(l+r)>>1;
l(p)=build(l,mid);r(p)=build(mid+1,r);
return p;
}
inline ll ins(ll cur,ll l,ll r,ll loc,ll val) {
ll p=++tot;
tree[p]=tree[cur];
if(l==r) {cnt(p)+=val;return p;}
ll mid=(l+r)>>1;
if(loc<=mid) {l(p)=ins(l(cur),l,mid,loc,val);}
else {r(p)=ins(r(cur),mid+1,r,loc,val);}
cnt(p)=cnt(l(p))+cnt(r(p));
return p;
}
inline ll getmax(ll L,ll R,ll l,ll r) {
if(l==r) {if(cnt(R)-cnt(L)>lim/2) return l;return 0;}
ll mid=(l+r)>>1,lcnt=cnt(l(R))-cnt(l(L));
if(lcnt>lim/2) return getmax(l(L),l(R),l,mid);
else return getmax(r(L),r(R),mid+1,r);
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
inline void writeln(ll x) {
write(x);putchar('\n');
}
int main() {
n=read();m=read();
for(ll i=1;i<=n;i++) {
a[i]=read();
}
rt[0]=build(1,n);
for(ll i=1;i<=n;i++) {
rt[i]=ins(rt[i-1],1,n,a[i],1);
}
while(m--) {
l=read();r=read();lim=r-l+1;
ll tmp=getmax(rt[l-1],rt[r],1,n);
writeln(tmp);
}
return 0;
}
|