The problem requires maintaining a sequence of n initial preferences and processing m dynamic updates. Each query defines a subarray [L, R], a fallback identifier F, and a list of K positions. The task is to identify whether any value appears strictly more than (R - L + 1) / 2 times within the specified range. If a strict majority exists, it becomes the query result; otherwise, F is selected. All K specified positions must then update their values to the chosen result. After processing all queries, the final majority element across the entire array [1, n] must be determined, with -1 reported if none exists.

Majority Element Identification

Moore’s Voting Algorithm provides an optimal method for detecting a potantial majority candidate in linear time. By tracking a current candidate and a balance counter, the algorithm pairs distinct elements to cancel each other out. If a value exceeds half the total count, it cannot be completely eliminated and will remain as the final candidate.

This elimination process is associative. For any partitioned interval, the balance and candidate from the left half can be combined with the right half using the same cancellation logic. Identical candidates accumulate their balances, while differing candidates subtract the smaller balance from the larger, retaining the identifier associated with the positive remainder. This property allows the voting mechanism to be embedded directly into a segment tree, reducing candidate proposal queries to O(log n).

Exact Verification via Order-Statistic Trees

The segment tree only yields a potential majority candidate. To confirm whether this candidate actualy satisfies the strict majority condition, exact frequency counting within [L, R] is required. Maintaining an independent sorted container for each possible value, storing the indices where that value appears, enables logarithmic range counting. By querying the number of stored indices less than or equal to R and subtracting those less than L, the exact occurrence count is retrieved efficiently. Policy-based data structures or balanced binary search trees are well-suited for this role.

Probabilistic Sampling Alternative

When a strict majority exists, it occupies more than 50% of any queried segment. Randomly sampling a fixed number of positions within [L, R] and checking their frequencies yields a high-probability detection strategy. With T independent trials, the probability of missing an existing majority drops below 2^{-T}. For practical constraints, T ≈ 20–25 is sufficient. This approach avoids segment tree construction and updates, relying solely on the index-tracking structure for verification and dynamic maintenance.

Deterministic Implementation: Segment Tree + Order-Statistic Tracking

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

using IndexRegistry = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int MAX_N = 500050;
constexpr int INF_SENTINEL = 1e9;

struct VotingNode {
    int candidate_id;
    int net_balance;
};

namespace SegmentQuerier {
    VotingNode tree_nodes[MAX_N << 2];

    VotingNode combine(const VotingNode& lhs, const VotingNode& rhs) {
        if (lhs.candidate_id == rhs.candidate_id) {
            return {lhs.candidate_id, lhs.net_balance + rhs.net_balance};
        }
        return (lhs.net_balance >= rhs.net_balance)
            ? VotingNode{lhs.candidate_id, lhs.net_balance - rhs.net_balance}
            : VotingNode{rhs.candidate_id, rhs.net_balance - lhs.net_balance};
    }

    void construct(int node_idx, int l, int r, const vector<int>& data) {
        if (l == r) {
            tree_nodes[node_idx] = {data[l], 1};
            return;
        }
        int mid = (l + r) >> 1;
        construct(node_idx << 1, l, mid, data);
        construct(node_idx << 1 | 1, mid + 1, r, data);
        tree_nodes[node_idx] = combine(tree_nodes[node_idx << 1], tree_nodes[node_idx << 1 | 1]);
    }

    void modify(int node_idx, int l, int r, int pos, int new_val) {
        if (l == r) {
            tree_nodes[node_idx] = {new_val, 1};
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) modify(node_idx << 1, l, mid, pos, new_val);
        else modify(node_idx << 1 | 1, mid + 1, r, pos, new_val);
        tree_nodes[node_idx] = combine(tree_nodes[node_idx << 1], tree_nodes[node_idx << 1 | 1]);
    }

    VotingNode extract(int node_idx, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree_nodes[node_idx];
        int mid = (l + r) >> 1;
        if (qr <= mid) return extract(node_idx << 1, l, mid, ql, qr);
        if (ql > mid) return extract(node_idx << 1 | 1, mid + 1, r, ql, qr);
        return combine(extract(node_idx << 1, l, mid, ql, qr),
                       extract(node_idx << 1 | 1, mid + 1, r, ql, qr));
    }
}

int active_choices[MAX_N];
IndexRegistry position_sets[MAX_N];

int compute_range_count(int cid, int left_bound, int right_bound) {
    return position_sets[cid].order_of_key(right_bound + 1) -
           position_sets[cid].order_of_key(left_bound);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int total_n, ops_m;
    cin >> total_n >> ops_m;

    vector<int> initial_arr(total_n + 1);
    for (int i = 1; i <= total_n; ++i) {
        cin >> initial_arr[i];
        active_choices[i] = initial_arr[i];
        position_sets[initial_arr[i]].insert(i);
    }

    SegmentQuerier::construct(1, 1, total_n, initial_arr);

    for (int i = 0; i < ops_m; ++i) {
        int L, R, fallback_id, update_count;
        cin >> L >> R >> fallback_id >> update_count;

        vector<int> targets(update_count);
        for (int& t : targets) cin >> t;

        VotingNode proposal = SegmentQuerier::extract(1, 1, total_n, L, R);
        int frequency = compute_range_count(proposal.candidate_id, L, R);
        int winner = (frequency > (R - L + 1) / 2) ? proposal.candidate_id : fallback_id;

        cout << winner << "\n";

        for (int pos : targets) {
            int prev_val = active_choices[pos];
            position_sets[prev_val].erase(pos);
            position_sets[winner].insert(pos);
            active_choices[pos] = winner;
            SegmentQuerier::modify(1, 1, total_n, pos, winner);
        }
    }

    VotingNode final_check = SegmentQuerier::extract(1, 1, total_n, 1, total_n);
    int final_freq = compute_range_count(final_check.candidate_id, 1, total_n);
    cout << (final_freq > total_n / 2 ? final_check.candidate_id : -1) << "\n";

    return 0;
}

Probabilistic Implementation: Random Sampling + Policy-Based Trees

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

using VoterLog = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int MAX_SZ = 500050;
int current_preference[MAX_SZ];
VoterLog supporter_indices[MAX_SZ];

inline int count_supporters(int candidate, int range_start, int range_end) {
    auto& log = supporter_indices[candidate];
    return log.order_of_key(range_end + 1) - log.order_of_key(range_start);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    mt19937 generator(chrono::steady_clock::now().time_since_epoch().count());

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        cin >> current_preference[i];
        supporter_indices[current_preference[i]].insert(i);
    }

    const int TRIAL_COUNT = 25;
    uniform_int_distribution<int> uniform_sampler(1, n);

    while (q--) {
        int l, r, default_c, shift_k;
        cin >> l >> r >> default_c >> shift_k;

        vector<int> shifting_voters(shift_k);
        for (int& v : shifting_voters) cin >> v;

        int segment_span = r - l + 1;
        int detected_candidate = -1;

        for (int t = 0; t < TRIAL_COUNT; ++t) {
            int random_idx = l + (uniform_sampler(generator) % segment_span);
            int c = current_preference[random_idx];
            if (count_supporters(c, l, r) > segment_span / 2) {
                detected_candidate = c;
                break;
            }
        }

        int round_winner = (detected_candidate == -1) ? default_c : detected_candidate;
        cout << round_winner << "\n";

        for (int pos : shifting_voters) {
            int old_val = current_preference[pos];
            supporter_indices[old_val].erase(pos);
            supporter_indices[round_winner].insert(pos);
            current_preference[pos] = round_winner;
        }
    }

    int global_len = n;
    int overall_winner = -1;
    for (int t = 0; t < TRIAL_COUNT; ++t) {
        int idx = 1 + (uniform_sampler(generator) % global_len);
        int c = current_preference[idx];
        if (count_supporters(c, 1, n) > n / 2) {
            overall_winner = c;
            break;
        }
    }
    cout << overall_winner << "\n";

    return 0;
}