Applicable Scenarios

• Offline problems where expanding intervals is easier to maintain than shrinking.
• Variants exist for "remove-only" Mo's algorithm.

Example Problem: P5906 [Template] Rollback Mo's Algorithm

Given an array, process multiple queries to find the maximum distance between two equal elements within a given interval.

Constraints: $1 \le n, m \le 2 \times 10^5$

Approach

• Sort queries using standard Mo's algorithm block sorting.
• For each block, maintain a current interval initialized to $[R_i+1, R_i]$.
• Handle queries with both endpoints in the same block using brute force $O(\sqrt{n})$ processing.
• Expand the right pointer and store temporary data, then move the left pointer to compute the result.
• After processing, reset the left pointer and revert changes to maintain consistency.

Time Complexity

$O(n \sqrt{n})$

Implemantation

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, block_size, a[N], block_id[N];
int ans[N];
unordered_map<int, int> first_pos, temp_first;

struct Query {
    int l, r, idx;
    bool operator<(const Query& o) const {
        return block_id[l] == block_id[o.l] ? r < o.r : l < o.l;
    }
} queries[N];

int calc(int l, int r) {
    temp_first.clear();
    int result = 0;
    for (int i = l; i <= r; ++i) {
        if (temp_first.find(a[i]) == temp_first.end())
            temp_first[a[i]] = i;
        else
            result = max(result, i - temp_first[a[i]]);
    }
    return result;
}

int main() {
    // Read input and initialize block IDs
    // Process queries using rollback logic
    return 0;
}

Alternative Problem: Historical Research

Compute $\max_A (A \times T_A)$, where $T_A$ is the count of element $A$ in the query interval.

Constraints: $1 \le n, m \le 10^5$, $1 \le A \le 10^9$

Optimized Strategy

• Use coordinate compression to reduce value range.
• Implement brute-force handling for intra-block queries.
• Maintain a rolling maximum while expanding intervals.

Code Snippet

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, block_size, a[N], block_id[N];
long long ans[N], current_max;
int freq[N];

struct Query {
    int l, r, idx;
    bool operator<(const Query& o) const {
        return block_id[l] == block_id[o.l] ? r < o.r : l < o.l;
    }
} queries[N];

long long brute_force(int l, int r) {
    unordered_map<int, int> cnt;
    long long res = 0;
    for (int i = l; i <= r; ++i)
        res = max(res, 1LL * a[i] * (++cnt[a[i]]));
    return res;
}

int main() {
    // Coordinate compression and block sorting
    // Implement rollback logic for query processing
    return 0;
}

Advanced Application: WC2022 - Bald Chief

Given a permutation, for each query $[l, r]$, compute the sum of absolute differences between adjacent elements after sorting the subarray.

Constraints: $1 \le n, m \le 5 \times 10^5$, Time Limit: 5s

Optimization Insight

• Use a linked list to maintain predecessor-successor relationships.
• Avoid logarithmic overhead by eliminating set-based tracking.
• Apply rollback technique to handle deletions efficiently.

Key Structures

struct DoublyLinkedList {
    int prev, next, value;
};