Kyselyt

#include <bits/stdc++.h>

using namespace std;

constexpr int N = (1 << 18);

int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }
int parent(int i) { return i / 2; }
int is_left(int i) { return (~i) & 1; }
int is_right(int i) { return i & 1; }
int is_root(int i) { return i == 1; }
int is_leaf(int i) { return i >= N; }

int main() {
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> luvut(n+1, -1);
    vector<pair<int, int>> kyselyt(q);
    vector<int> tulokset(q);
    vector<int> kyselyt_lopun_mukaan(q);
    unordered_map<int, int> luvut_alkuperäiseksi;
    unordered_map<int, int> luvut_tiivisteeksi;

    for (int i = 1; i <= n; i++) {
        int j0;
        cin >> j0;
        int j1 = luvut_tiivisteeksi[j0];
        luvut_tiivisteeksi[j0] = j1 = (j1 ? j1 : (int)luvut_tiivisteeksi.size());
        luvut[i] = j1;
        luvut_alkuperäiseksi[j1] = j0;
    }
    luvut_alkuperäiseksi[-1] = -1;

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        kyselyt[i] = {a, b};
        kyselyt_lopun_mukaan[i] = i;
    }
    sort(kyselyt_lopun_mukaan.begin(), kyselyt_lopun_mukaan.end(), [&](int a, int b) { return kyselyt[a].second < kyselyt[b].second; });

    const int M = luvut_tiivisteeksi.size() + 1;
    vector<int> yli_puolet(N + (n+2), -1);
    vector<map<int, int>> summataulu(M);
    vector<int> määrätaulu(M);

    auto summataulu_range_sum = [&](int luku, int a, int b) {
        auto it_a = prev(summataulu[luku].lower_bound(a));
        auto it_b = summataulu[luku].rbegin();
        int val_a = it_a->second;
        int val_b = it_b->second;
        return val_b - val_a;
    };

    auto summataulu_yli_puolet = [&](int luku, int a0, int b0) {
        if (luku == -1 || määrätaulu[luku] <= (b0 - a0 + 1) / 2) {
            return false;
        }
        return summataulu_range_sum(luku, a0, b0) > (b0 - a0 + 1) / 2;
    };

    auto binary_tree_result = [&](int a0, int b0) {
        int a = a0 + N, b = b0 + N;
        unordered_set<int> tutkitut;
        auto tutki = [&](int x) {
            if (!tutkitut.count(x) && summataulu_yli_puolet(x, a0, b0)) {
                return true;
            }
            tutkitut.insert(x);
            return false;
        };
        while (a <= b) {
            if (is_right(a)) {
                if (tutki(yli_puolet[a])) {
                    return yli_puolet[a];
                }
                a++;
            }
            if (is_left(b)) {
                if (tutki(yli_puolet[b])) {
                    return yli_puolet[b];
                }
                b--;
            }
            a = parent(a);
            b = parent(b);
        }
        return -1;
    };

    auto binary_tree_set = [&](int pos, int val) {
        int mask = 0;
        int i = pos + N;
        yli_puolet[i] = val;
        while ((i = parent(i))) {
            mask = 2 * mask + 1;
            int res_a = yli_puolet[left(i)];
            int res_b = yli_puolet[right(i)];
            int a = pos & ~mask, b = pos | mask;
            if (res_a == res_b || summataulu_yli_puolet(res_a, a, b)) {
                yli_puolet[i] = res_a;
            } else if (summataulu_yli_puolet(res_b, a, b)) {
                yli_puolet[i] = res_b;
            } else {
                yli_puolet[i] = -1;
            }
        }
    };

    for (int i = 1; i <= n; i++) {
        binary_tree_set(i, luvut[i]);
    }

    int luku_i = 0;
    for (int i: kyselyt_lopun_mukaan) {
        int a, b;
        tie(a, b) = kyselyt[i];
        while (luku_i < b) {
            luku_i++;
            auto x = luvut[luku_i];
            auto &t = summataulu[x];
            if (t.empty()) {
                t[0] = 0;
            }
            t[luku_i] = t.rbegin()->second + 1;
            määrätaulu[x] += 1;
            binary_tree_set(luku_i, x);
        }
        int vastaus = binary_tree_result(a, b);
        tulokset[i] = luvut_alkuperäiseksi[vastaus];
    }
    for (int i: tulokset) {
        cout << i << "\n";
    }
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: ACCEPTED

Test 10

Group: 4

Verdict: ACCEPTED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: ACCEPTED

Test 13

Group: 3, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED