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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
do { \
std::cerr << #variable << ":"; \
for (const auto& elem : variable) { \
std::cerr << elem << " "; \
} \
std::cerr << "\n"; \
} while (0)
#define uniVec(var) \
do { \
sort(var.begin(),var.end());\
var.resize(unique(var.begin(),var.end())-var.begin());\
} while (0)
#define debugN(var,N) \
do{ \
std::cerr<<#var<<":"; \
FOR(i,1,N){ \
std::cerr<<var[i]<<" "; \
} \
std::cerr<<"\n"; \
}while(0)
#define debugMap(variable) \
do { \
std::cerr << #variable << ":\n"; \
for (const auto& pair : variable) { \
std::cerr << " " << pair.first << " => " << pair.second << "\n"; \
} \
std::cerr << std::endl; \
} while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x)) // vec中大于x的数有几个
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN];
/*
*/
struct persisTree{ // 单点修改区间查询的主席树，处理静态区间第 k 小问题。
// 由于太大了，该结构体只能声明与全局变量作用域
// 测试 https://www.luogu.com.cn/record/218615977 （只测了单次数据）
// maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
static const int maxn=static_cast<int>(5e5)+7,maxm=static_cast<int>(5e5)+7;
static const int LOGmxm=19; // 这个版本次数一般也不会超过2**20，也就是1048576
static const int maxn4=maxn*4+LOGmxm*maxn;
int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
int arr[maxn],sum[maxn4];
int n=0,m=0,idx=1,Cver=0,len=0;
int li[maxn];
// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
inline void init(int ln,int lm){
// int lmaxn4=ln*4+log2(ln)*lm+5;
idx=1,n=ln,m=lm,Cver=0;
root[0]=1; // 版本0的根是1
}
inline int initLi(){ // 离散化操作
for(int i=1;i<=n;++i){
li[i]=arr[i];
}
sort(li+1,li+1+n);
len=unique(li+1,li+1+n)-li-1; // 这个len是超了一个的
return len;
}
inline int kth(ll x){
int ret=lower_bound(li+1,li+1+len,x)-li;
return ret;
}
inline void clone(int node){
++idx;
L[idx]=L[node];
R[idx]=R[node];
sum[idx]=sum[node];
ls[idx]=ls[node];
rs[idx]=rs[node];
}
void build(int node,int l,int r){
ls[node]=++idx;
rs[node]=++idx;
L[node]=l;
R[node]=r;
sum[node]=0;
if(l==r) return;
build(ls[node],l,((l+r)>>1));
build(rs[node],(l+r>>1)+1,r);
}
// 处理静态区间第 k 小问题中，因为权值线段树，x=1
void add(int node,int ver,int p,ll x){
clone(node);
sum[idx]+=x;
// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
if(root[ver]==node){
++Cver;
root[Cver]=idx;
}
if(p==L[node] && p==R[node]){
return;
}
if(p>=L[ls[node]] && p<=R[ls[node]]){
int nals=ls[idx];
ls[idx]=idx+1;
add(nals,ver,p,x);
}else{
int nars=rs[idx];
rs[idx]=idx+1;
add(nars,ver,p,x);
}
}
// 我们要查询是否有一个数出现次数超过一半
int query(int u,int v,int l,int r,int k){
// #ifdef LOCAL
// debug(u);
// debug(L[u]);
// debug(R[u]);
// debug(sum[u]);
// debug(v);
// debug(L[v]);
// debug(R[v]);
// debug(sum[v]);
//
// #endif
if(l==r){
if(sum[v]-sum[u]>=k) return l;
else return 0;
}
// 我们这样就知道了
int lsum=sum[ls[v]]-sum[ls[u]];
// #ifdef LOCAL
// debug(lsum);
// debug(k);
// cerr<<"\n";
// #endif
int mid=l+r>>1;
if(lsum>=k){
return query(ls[u],ls[v],l,mid,k);
}else{
return query(rs[u],rs[v],mid+1,r,k);
}
}
};
persisTree tr;
inline void solve(){
// N=read(),M=read();
scanf("%lld%lld",&N,&M);
// cin>>N>>M;
tr.init(N,N);
FOR(i,1,N){
// tr.arr[i]=read();
scanf("%d",&tr.arr[i]);
}
int len=tr.initLi();
tr.build(1,1,len);
FOR(i,1,N){
tr.add(tr.root[i-1],i-1,tr.kth(tr.arr[i]),1);
}
FOR(_,1,M){
// ll l=read(),r=read();
ll l,r;
scanf("%lld%lld",&l,&r);
ll mid=(r-l+1)/2+1;
// #ifdef LOCAL
// debug(mid);
// #endif
int ans=tr.li[tr.query(tr.root[l-1],tr.root[r],1,len,mid)];
// write(ans);
// putchar('\n');
// cout<<ans<<"\n";
printf("%d\n",ans);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://www.luogu.com.cn/record/218724163
1 1
1
1 1
*/
|