Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef LOCAL
- #include <iostream>
- #include <fstream>
- #include <iomanip>
- #include <random>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <set>
- #include <map>
- #else
- #include <bits/stdc++.h>
- #define cerr if (false) cerr
- #define endl '\n'
- #endif
- #define fi first
- #define se second
- #define sz(a) ((int)(a).size())
- #define all(a) (a).begin(), (a).end()
- #define lsb(x) (x & (-x))
- #define bit(mask, i) (((mask) >> (i)) & 1)
- #define popcount(x) __builtin_popcount(x)
- #define YES cout << "YES" << endl
- #define NO cout << "NO" << endl
- using namespace std;
- template <typename T>
- bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
- template <typename T>
- bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }
- using ll = long long;
- using pii = pair<int, int>;
- const int NMAX = 2e5+5;
- const int NIL = -1;
- struct PerSegTree {
- struct Node {
- int cnt, lchild, rchild;
- };
- int n;
- vector<Node> v;
- vector<int> root;
- PerSegTree(int _n): n(_n), root({ build(1, n) }) { }
- int build(int l, int r) {
- if (l >= r) {
- Node node = { 0, NIL, NIL };
- v.push_back(node);
- return sz(v) - 1;
- }
- int mid = (l + r) >> 1;
- Node node = { 0, build(l, mid), build(mid + 1, r) };
- v.push_back(node);
- return sz(v) - 1;
- }
- void update_val(int k, int pos, int val) {
- root[k] = update_val(root[k], 1, n, pos, val);
- }
- int update_val(int u, int l, int r, int pos, int val) {
- if (pos < l || r < pos) return u;
- if (l >= r) {
- Node node = { val, NIL, NIL };
- v.push_back(node);
- return sz(v) - 1;
- }
- int mid = (l + r) >> 1;
- Node node = { 0,
- update_val(v[u].lchild, l, mid, pos, val),
- update_val(v[u].rchild, mid + 1, r, pos, val)
- };
- node.cnt = v[node.lchild].cnt + v[node.rchild].cnt;
- v.push_back(node);
- return sz(v) - 1;
- }
- int query_cnt_greater(int k, int l, int r) {
- return r - l + 1 - query_cnt(root[k - 1], 1, n, l, r);
- }
- int query_cnt(int u, int l, int r, int ll, int rr) {
- if (ll <= l && r <= rr)
- return v[u].cnt;
- int mid = (l + r) >> 1;
- int cnt = 0;
- if (ll <= mid) cnt = query_cnt(v[u].lchild, l, mid, ll, rr);
- if (mid < rr) cnt += query_cnt(v[u].rchild, mid + 1, r, ll, rr);
- return cnt;
- }
- void update_copy(int k) {
- v.push_back(v[root[k]]);
- root.push_back(sz(v) - 1);
- }
- };
- int n, m, max_val;
- vector<int> a[NMAX];
- void read() {
- cin >> n >> m;
- for (int i = 1, x; i <= n; i++) {
- cin >> x;
- max_val = max(max_val, x);
- a[x].push_back(i);
- }
- }
- int query(PerSegTree &tree, int ll, int rr) {
- int l = 1, r = max_val;
- while (l <= r) {
- int mid = (l + r) >> 1;
- if (tree.query_cnt_greater(mid, ll, rr) >= mid) l = mid + 1;
- else r = mid - 1;
- }
- return r;
- }
- void solve() {
- PerSegTree tree(n);
- for (int val = 1; val <= max_val; val++) {
- tree.update_copy(val - 1);
- for (auto &pos : a[val])
- tree.update_val(val, pos, 1);
- }
- while (m--) {
- int l, r;
- cin >> l >> r;
- cout << query(tree, l, r) << endl;
- }
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement