#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, q, a[N], ans[N];
int bit[N];
struct query {
int l, r, id;
};
vector<int> pos[N];
vector<query> queries;
void update(int i, int val) {
for(; i < ar; i += i & -i) bit[i] += val;
}
int get(int i) {
int res = 0;
for(; i; i -= i & -i) res += bit[i];
return res;
}
int Sum(int l, int r) {
return get(r) - get(l - 1);
}
void solve(int l, int r, vector<query> &queries) {
if(queries.empty()) return;
if(l == r) {
for(auto it : queries) ans[it.id] = l;
return;
}
vector<query> L, R;
int mid = l + r >> 1;
for(int i = mid + 1; i <= r; ++i) {
for(int j : pos[i]) update(j, 1);
}
for(auto it : queries) {
if(Sum(it.l, it.r) > mid) R.push_back(it);
else L.push_back(it);
}
solve(l, mid, L);
for(int i = mid + 1; i <= r; ++i) {
for(int j : pos[i]) update(j, -1);
}
solve(mid + 1, r, R);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
pos[a[i]].push_back(i);
}
for(int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
queries.push_back({l, r, i});
}
solve(1, (int)2e5, queries);
for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
return 0;
}
// https://oj.vnoi.info/problem/coci2021_r6_index
Compilation message
index.cpp: In function 'void update(int, int)':
index.cpp:16:15: error: 'ar' was not declared in this scope; did you mean 'a'?
16 | for(; i < ar; i += i & -i) bit[i] += val;
| ^~
| a
index.cpp: In function 'void solve(int, int, std::vector<query>&)':
index.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = l + r >> 1;
| ~~^~~
