Replace
Repeatedly replace an interval by the minimum and maximum values inside it, and find the first time it becomes [1, n].
Problem Summary
Original task summary for this archive page. The official Codeforces statement is linked in the header instead of being mirrored here.
An interval \([l,r]\) is transformed into \[ f([l,r]) = [\min(a_l,\dots,a_r), \max(a_l,\dots,a_r)]. \] For each query interval, we need the minimum number of repeated applications of \(f\) needed to reach \([1,n]\), or report that this never happens.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Motivation
The function is not local in the usual sense: one application can move the interval far away, and naive simulation for every query is far too slow.
The hard part is finding a state description that can be lifted by powers of two.
Key Observations
For a singleton interval \([i,i]\), the next state is just \([a_i,a_i]\). So singleton states are simple function composition on indices.
The nontrivial states are intervals of length at least \(2\). For those, it is enough to understand what happens to adjacent pairs \([i,i+1]\).
If two source intervals overlap at some index \(x\), then after applying \(f\), both resulting intervals contain \(a_x\). So overlapping source intervals always map to overlapping destination intervals.
Because of that overlap property, the images of consecutive adjacent pairs remain a chain of overlapping intervals at every power of two.
Derivation
Define \[ g_t(i) = f^{2^t}([i,i+1]) \] for \(1 \le i < n\), and \[ p_t(i) = f^{2^t}([i,i]) \] for singleton states.
The singleton transition is immediate: \[ p_0(i) = [a_i,a_i], \qquad p_{t+1}(i) = p_t(a_i) \text{ on the index level}. \] So we can store only the index reached by a singleton after \(2^t\) steps.
Now look at any interval \([l,r]\) with \(l < r\). After one step, \[ f([l,r]) = \bigcup_{i=l}^{r-1} f([i,i+1]) \] in the interval sense: the minimum over the whole segment is the minimum of the pair-minima, and similarly for the maximum.
The same remains true after every power of two. Inductively, the intervals \(g_t(l), g_t(l+1), \dots, g_t(r-1)\) overlap consecutively, so their union is again one interval. Applying \(f\) to that union is the same as taking the hull of the next-step images of those pair intervals. Therefore \[ f^{2^t}([l,r]) = \operatorname{hull}_{i=l}^{r-1} g_t(i). \]
That identity is the whole problem. Once every \(g_t(i)\) is known, any jump by \(2^t\) steps becomes:
a singleton jump if the current interval has length \(1\)
one range-hull query over the array \(g_t\) otherwise
Algorithm
Precompute singleton jumps \(p_t\) by repeated composition.
Precompute pair jumps \(g_t\). To build \(g_{t+1}(i)\):
if \(g_t(i)\) is already a singleton \([x,x]\), then \(g_{t+1}(i) = p_t(x)\)
otherwise \(g_{t+1}(i)\) is the hull of \(g_t(x)\) for all adjacent pairs inside that interval, so one range query on level \(t\) is enough
Use a sparse table on each level to answer those hull queries in \(O(1)\).
For each query, binary-lift on the number of applications: keep the current interval, try to add powers of two from large to small, and only accept a jump if it still does not reach \([1,n]\). enumerate
Why It Works
The preprocessing is correct because it stores exactly the result of \(2^t\) applications for every adjacent pair and every singleton.
The range-hull formula is correct because consecutive pair-images always overlap, so their union stays an interval, and applying \(f\) to that interval only depends on the minimum left endpoint and the maximum right endpoint among the next-step pieces.
Binary lifting works because once \([1,n]\) is reached, it becomes a fixed point. Reaching \([1,n]\) means the array contains both values \(1\) and \(n\), hence the minimum and maximum over the full interval are still \(1\) and \(n\). So the predicate ``already reached \([1,n]\)'' is monotone in the number of steps.
Pseudocode
Natural algorithm flow before the concrete implementation.
Read \(n\), the array, and the queries.
Precompute singleton jumps for powers of two. Precompute pair jumps for powers of two:
build a sparse table for the current pair level
for each adjacent pair image:
if it is a singleton, advance it with the singleton table
otherwise query the hull of all pair images inside that interval
For each query:
if it is already \([1,n]\), print \(0\)
if it is a singleton and \(n > 1\), print \(-1\)
otherwise try powers of two from large to small
keep every jump that still avoids \([1,n]\)
after the loop, check whether one more step reaches \([1,n]\)
Complexity Analysis
Time and memory costs for the exact implementation shown below.
Preprocessing pair levels with sparse tables: \(O(n \log^2 n)\)
Query phase: \(O(q \log n)\) once the levels are ready, plus another \(O(n \log^2 n)\) for the transient sparse tables used during binary lifting
Memory: \(O(n \log n)\)
C++ Solution
The exact repository source used for this solution page.
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int MAX_LOG = 34;
struct Interval {
int left;
int right;
};
Interval merge_intervals(const Interval& first, const Interval& second) {
return {min(first.left, second.left), max(first.right, second.right)};
}
bool operator==(const Interval& first, const Interval& second) {
return first.left == second.left && first.right == second.right;
}
struct SparseTable {
vector<int> logs;
vector<vector<Interval>> table;
void build(const vector<Interval>& values, int size) {
logs.assign(size + 1, 0);
for (int i = 2; i <= size; ++i) {
logs[i] = logs[i / 2] + 1;
}
const int levels = logs[size] + 1;
table.assign(levels, vector<Interval>(size + 1));
for (int i = 1; i <= size; ++i) {
table[0][i] = values[i];
}
for (int level = 1; level < levels; ++level) {
const int length = 1 << level;
const int half = length >> 1;
for (int i = 1; i + length - 1 <= size; ++i) {
table[level][i] = merge_intervals(table[level - 1][i], table[level - 1][i + half]);
}
}
}
Interval query(int left, int right) const {
const int level = logs[right - left + 1];
return merge_intervals(table[level][left], table[level][right - (1 << level) + 1]);
}
};
Interval advance_interval(
const Interval& current,
int level,
const SparseTable& sparse,
const vector<vector<int>>& single_jumps
) {
if (current.left == current.right) {
const int next_index = single_jumps[level][current.left];
return {next_index, next_index};
}
return sparse.query(current.left, current.right - 1);
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
if (n == 1) {
while (q--) {
int left, right;
cin >> left >> right;
cout << 0 << '\n';
}
return 0;
}
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
vector<pair<int, int>> queries(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].first >> queries[i].second;
}
vector<vector<int>> single_jumps(MAX_LOG, vector<int>(n + 1));
for (int i = 1; i <= n; ++i) {
single_jumps[0][i] = a[i];
}
for (int level = 0; level + 1 < MAX_LOG; ++level) {
for (int i = 1; i <= n; ++i) {
single_jumps[level + 1][i] = single_jumps[level][single_jumps[level][i]];
}
}
vector<vector<Interval>> pair_jumps(MAX_LOG, vector<Interval>(n));
for (int i = 1; i < n; ++i) {
pair_jumps[0][i] = {min(a[i], a[i + 1]), max(a[i], a[i + 1])};
}
SparseTable sparse;
for (int level = 0; level + 1 < MAX_LOG; ++level) {
sparse.build(pair_jumps[level], n - 1);
for (int i = 1; i < n; ++i) {
const Interval current = pair_jumps[level][i];
if (current.left == current.right) {
const int next_index = single_jumps[level][current.left];
pair_jumps[level + 1][i] = {next_index, next_index};
} else {
pair_jumps[level + 1][i] = sparse.query(current.left, current.right - 1);
}
}
}
vector<long long> answers(q, -1);
vector<Interval> current(q);
vector<char> active(q, false);
const Interval target{1, n};
for (int i = 0; i < q; ++i) {
const int left = queries[i].first;
const int right = queries[i].second;
if (left == 1 && right == n) {
answers[i] = 0;
} else if (left == right) {
answers[i] = -1;
} else {
current[i] = Interval{left, right};
answers[i] = 0;
active[i] = true;
}
}
for (int level = MAX_LOG - 1; level >= 0; --level) {
sparse.build(pair_jumps[level], n - 1);
for (int i = 0; i < q; ++i) {
if (!active[i]) {
continue;
}
const Interval next = advance_interval(current[i], level, sparse, single_jumps);
if (!(next == target)) {
answers[i] += 1LL << level;
current[i] = next;
}
}
}
sparse.build(pair_jumps[0], n - 1);
for (int i = 0; i < q; ++i) {
if (!active[i]) {
continue;
}
const Interval next = advance_interval(current[i], 0, sparse, single_jumps);
answers[i] = (next == target ? answers[i] + 1 : -1);
}
for (long long answer : answers) {
cout << answer << '\n';
}
return 0;
}
Pitfalls
Edge cases and implementation traps worth checking before reusing the idea in contest code.
A singleton query can never become \([1,n]\) when \(n > 1\), because singleton states always stay singletons.
The implementation uses \(34\) lifting levels. That is safely above the number of distinct interval states for \(n \le 10^5\).
The merge operation is just interval hull: take the minimum left endpoint and the maximum right endpoint.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.