Optimizing Subarray Frequency Queries

Determining the most frequent element's count within arbitrary subranges presents a challenge for standard data structures due to non-additive merge properties. While segment trees struggle here, offline processing via Mo's algorithm (square root decomposition of queries) provides an efficient solution.

Reducing Transition Complexity

A naive implemantation tracks frequencies in a hash map or array and maintains a multiset of these values to query the maximum frequency. This incurs $O(\log n)$ overhead per pointer move. To achieve amortized $O(1)$ transitions, maintain two auxiliary arrays:

1. freq[x]: The currant occurrence count of value x.
2. cnt[k]: The number of distinct values that appear exactly k times.

By tracking the global maximum frequency (max_freq), updates become straightforward. When increasing the frequency of a value x, decrement cnt[old], increment freq[x], and update cnt[new]. Adjust max_freq upwards if necessary. Decreasing frequency requires checking if cnt[max_freq] drops to zero; if so, decrement max_freq until a valid bucket is found. Since the total number of increments equals the number of decrements across the entire run, the while loop logic runs amortized constant time.

int n, q;
std::cin >> n >> q;
std::vector<int> arr(n + 1);
for (int i = 1; i <= n; ++i) std::cin >> arr[i];

struct Query { int l, r, id; };
std::vector<Query> qs(q);
for (int i = 0; i < q; ++i) std::cin >> qs[i].l >> qs[i].r >> qs[i].id;

int block_size = static_cast<int>(std::sqrt(n)) + 1;
std::sort(qs.begin(), qs.end(), [block_size](const Query& a, const Query& b) {
    if (a.l / block_size != b.l / block_size)
        return a.l / block_size < b.l / block_size;
    return (a.l / block_size & 1) ? a.r < b.r : a.r > b.r;
});

std::vector<int> freq(n + 1, 0);
std::vector<int> cnt(n + 1, 0);
cnt[0] = 1e9; 
int current_max = 0;
auto add_pos = [&](int pos) {
    int val = arr[pos];
    cnt[freq[val]]--;
    freq[val]++;
    cnt[freq[val]]++;
    current_max = std::max(current_max, freq[val]);
};
auto remove_pos = [&](int pos) {
    int val = arr[pos];
    cnt[freq[val]]--;
    freq[val]--;
    cnt[freq[val]]++;
    while (cnt[current_max] == 0) current_max--;
};

std::vector<int> ans(q);
int L = 1, R = 0;
for (const auto& qry : qs) {
    while (R < qry.r) add_pos(++R);
    while (L > qry.l) add_pos(--L);
    while (R > qry.r) remove_pos(R--);
    while (L < qry.l) remove_pos(L++);
    ans[qry.id] = current_max;
}

for (int i = 0; i < q; ++i) std::cout << ans[i] << "\n";

Jump Simulation with Square Root Decomposition

In scenarios where moving from index $i$ always forwards to $i + a_i$, we often need to answer how many steps are required to exceed bounds $n$. Dynamic modifications to offsets $a_i$ complicate direct simulation.

Block Precomputation Strategy

Divide the array into blocks of size $B \approx \sqrt{n}$. For each position $i$, store:

• jump_target[i]: The first index reached outside the current block.
• jump_steps[i]: The step count required to reach jump_target[i].

Precomputation iterates backwards within each block. If jumping from $i$ lands outside the block, record 1 step and the destination. Otherwise, inherit the value from the landing spot plus one step.

Query and Update

Query: Start at $x$. Accumulate jump_steps[x] and jump to jump_target[x]. Repeat until the target exceeds $n$. Add the final partial steps manually. Update: Changing $a_x$ invalidates precomputed values only within its specific block. Re-run the backward precomputation for that block range ($O(B)$).

Total complexity: $O(q\sqrt{n})$. Implementation uses vectors for storage and processes indices logically rather than relying on hard-coded boundaries.

void solve() {
    int n; std::cin >> n;
    int B = static_cast<int>(std::sqrt(n)) + 1;
    std::vector<int> moves(n + 1);
    std::vector<int> pos_map(n + 1);
    std::vector<int> blk_start(n + 1), blk_end(n + 1);
    std::vector<int> steps(n + 1, 0);
    std::vector<int> targets(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        std::cin >> moves[i];
        pos_map[i] = (i - 1) / B;
        if (pos_map[i] == 0 || (i - 1) % B == 0) blk_start[pos_map[i]] = i;
        blk_end[pos_map[i]] = i;
    }

    // Recompute block info
    auto refresh_block = [&](int p_idx) {
        int start = blk_start[p_idx];
        int end = blk_end[p_idx];
        for (int i = end; i >= start; --i) {
            int next_idx = i + moves[i];
            if (next_idx > end) {
                steps[i] = 1;
                targets[i] = next_idx;
            } else {
                steps[i] = 1 + steps[next_idx];
                targets[i] = targets[next_idx];
            }
        }
    };

    // Initial refresh for all blocks
    int max_blk = pos_map[n];
    for (int k = 0; k <= max_blk; ++k) refresh_block(k);

    int q_ops; std::cin >> q_ops;
    while (q_ops--) {
        int op, x; std::cin >> op >> x;
        if (op == 1) {
            long long res = 0;
            while (x <= n) {
                res += steps[x];
                x = targets[x];
            }
            std::cout << res << "\n";
        } else {
            int y; std::cin >> y;
            moves[x] = y;
            refresh_block(pos_map[x]);
        }
    }
}

Summing Minimums Over Subranges

Calculating $\sum_{l \le i \le j \le r} \min(a[i..j])$ efficiently requires combining Monotonic Stacks with Mo's Algorithm.

Mathematical Insight

Let $f(i)$ be the sum of minimums of all suffixes ending at $i$. Using a monotonic stack, find $prev_smaller[i]$ (nearest index to left with smaller value). Then: $$ f(i) = f(prev_smaller[i]) + (i - prev_smaller[i]) \times a[i] $$ Similarly, calculate $g(i)$ based on $next_smaller[i]$ (nearest index to right with smaller value).

Integration into Mo's Algorithm

When expanding the window, finding the new minimum's position $p$ allows $O(1)$ calculation of the added contribution using prefix sums derived from $f$ and $g$. Specifically:

• Move Right ($R \to R+1$): Find min in new range $[L, R+1]$ at index $p$. Contribution adds $(p - L + 1) \times a[p] + (f[R+1] - f[p])$.
• Move Left ($L \to L-1$): Symmetric logic applies using $g[L]$.

An Sparse Table (ST) handles range minimum queries to locate $p$ instantly during moves.

// ST Construction omitted for brevity, assume get_min_pos(l, r) available
long long calc_move_right(int L, int R, int idx) {
    // idx is the position of new minimum in [L, R]
    long long term1 = (idx - L + 1LL) * arr[idx];
    long long term2 = suffix_sum_min[R] - suffix_sum_min[idx];
    return term1 + term2;
}

long long calc_move_left(int L, int R, int idx) {
    // idx is position of new minimum in [L, R]
    long long term1 = (R - idx + 1LL) * arr[idx];
    long long term2 = prefix_sum_min[L] - prefix_sum_min[idx];
    return term1 + term2;
}

// Inside Mo's loop
int cur_min_pos = get_st_min(cur_l, cur_r);
while (cur_r < q.r) cur_min_pos = get_st_min(cur_l, ++cur_r); res += calc_move_right(cur_l, cur_r, cur_min_pos);
// ... similar for other directions

Composite Problem Patterns

Complex competitive programming problems often layer multiple techniques. A typical example involves transforming constraints to fit known algorithms.

Transformation Tricks

If the goal is to find the longest arithmetic progression-like segment with difference $d$, subtract indices from values to normalize the sequence. A problem asking for modfiication costs to fix a sequence can often be restated as finding the mode in a transformed window. Sliding window techniques combined with block-based counting apply directly here.

Algorithm Layering

Some tasks require mixing RMQ, DP, and SQRT decomposition. For instance, querying aggregate statistics over dynamic ranges might combine:

1. Block Decomposition for the structure of queries.
2. Monotonic Stack / Precomputation for value properties within blocks.
3. Mo's Logic to handle the interdependence of query parameters.

Such hybrid approaches ensure that neither pure brute force nor simple static structures suffice, demanding flexibility in data organization and transition function design. By abstracting the core requirements—frequency tracking, jump simulation, or extremum summation—these diverse problems converge into manageable solutions under the unified umbrella of square-root algorithms.