v. Subarray Aggregates and Mex

Two families of “over all subarrays” problems. Both rest on the fact that the aggregate changes few times as the left end moves.

Few distinct values per right end

Fix the right end $r$ and move $l$ leftwards. Then $\gcd (a_l..a_r)$ changes $O(\log V)$ times, because each change at least halves it. $\mathrm{OR}$ and $\mathrm{AND}$ change $O(\log V)$ times, because each change sets or clears a bit. LCM changes $O(\log V)$ times while it stays below a bound $V$. (Min and max do not have this property; use a monotonic stack for those.)

Proof: gcd, OR, AND and (bounded) LCM change $O(\log V)$ times as $l$ decreases

Let $g_l=\mathrm{op}(a_l,\dots ,a_r)$ for fixed $r$, as $l$ runs from $r$ down to $0$. gcd: $g_{l-1}=\gcd (g_l,a_{l-1})$ divides $g_l$, so each step either keeps $g_l$ unchanged or strictly decreases it to a proper divisor, which is at most half of $g_l$ (a proper divisor of $x$ is at most $x/2$, since the next smaller divisor-multiple is $\le x/2$). A strictly positive integer can halve at most $O(\log V)$ times before reaching $1$, so gcd changes value at most $O(\log V)$ times. OR: $g_{l-1}=g_l\mathrm{OR}{a}_{l-1}\supseteq g_l$ (as a bitset), so the value only ever gains set bits or stays the same; since there are $O(\log V)$ bits, it changes at most $O(\log V)$ times. AND: symmetric, only loses set bits, same bound. LCM: $g_{l-1}=\mathrm{lcm}(g_l,a_{l-1})$ is a multiple of $g_l$, so each change at least doubles it (the next distinct multiple of $g_l$ that is itself a multiple structure is at least $2g_l$), and it’s capped by $V$, giving $O(\log V)$ changes before exceeding the cap. $■$

Keep the list of (value, number of left ends) runs for the current $r$ and extend it by $a_r$:

// runs: (value of op(a[l..r]), count of l giving it), most recent first
template<class Op> map<ll, ll> countByValue(const vector<ll>& a, Op op) {
    map<ll, ll> total;
    vector<pair<ll, ll>> cur;
    for (ll x : a) {
        vector<pair<ll, ll>> nxt = {{x, 1}};
        for (auto [v, c] : cur) {
            ll w = op(v, x);
            if (w == nxt.back().first) nxt.back().second += c; else nxt.push_back({w, c});
        }
        cur = move(nxt);
        for (auto [v, c] : cur) total[v] += c;
    }
    return total;
}

That’s $O(n\log V)$ operations (gcd costs another $\log$ in theory, but each chain of gcds telescopes to $O(\log V)$ total per position).

Uses:

• count subarrays with gcd (or OR, AND) equal to $g$, for many queries $g$;
• number of distinct ORs over all subarrays;
• sum over all subarrays of gcd times length: store the leftmost $l$ of each run;
• shortest or longest subarray with gcd $=g$ ending at $r$;
• “is there a subarray with gcd $=1$ / OR $=x$”, and minimum length;
• range queries “how many subarrays inside $[L,R]$ have gcd $=1$”: sweep $r$, and runs become range-add events on a BIT indexed by $l$.

Two pointers with gcd: gcd isn’t invertible, so the window needs a two-stack queue or a sparse table. With a sparse table, $\gcd (l..r)$ is $O(1)$ for a static array, since overlapping ranges are harmless for gcd.

Mex over subarrays

The mex of a set is the smallest non-negative integer not in it.

Mex of the whole array with updates: keep cnt[v] for $v\le n$ and a segment tree (or a set of absent values) over $[0,n]$ that finds the first $v$ with cnt[v] == 0. Values larger than $n$ never matter, since the mex is at most $n$.

Mex of a query range, offline: sweep $r$ and maintain last[v] = last position of $v$ in a segment tree over values storing the minimum of last. The mex of $[l,r]$ is the first $v$ with last[v] < l, found by descending. Make it persistent over $r$ to answer online. $O((n+q)\log n)$.

Proof: the min-of-last-occurrence tree finds the mex

At sweep position $r$, last[v] is the most recent index $\le r$ where value $v$ occurs (or $-\infty$ if $v$ never occurred up to $r$). A value $v$ lies in the range $[l,r]$ iff its most recent occurrence up to $r$ is $\ge l$, i.e. iff last[v] >= l; so $v$ is absent from $[l,r]$ iff last[v] < l. The mex of $[l,r]$ is by definition the smallest $v\ge 0$ absent from it, i.e. the smallest $v$ with last[v] < l — and since the segment tree stores the minimum of last over each value-range, descending toward the side whose minimum is $<l$ at every level finds exactly the smallest such $v$ (if the minimum over the whole range $[0,v_{\max }]$ is $\ge l$, every value up to $v_{\max }$ is present and the mex exceeds the tree’s domain, which the construction caps at $n$ since the mex of any range of length $\le n$ is at most $n$). Persisting one version of the tree per sweep position $r$ lets a later query re-run this same descent against the tree as it stood at that $r$, answering online. $■$

Which values are mexes of some subarray (CF 1436E): $m$ is the mex of some subarray iff some maximal segment avoiding $m$ (between consecutive occurrences of $m$, or before the first or after the last) contains all of $\mathrm{0..}m-1$. Sweep with the same “min of last positions over $[0,m)$” tree, and check each gap when its closing occurrence of $m$ arrives. $O(n\log n)$.

Proof: the CF 1436E criterion

($\Leftarrow$) If a maximal $m$-avoiding segment $[l,r]$ contains all of $0,\dots ,m-1$, then $[l,r]$‘s mex is exactly $m$: every value $<m$ is present (given) and $m$ itself is absent (the segment avoids $m$ by construction), so $m$ is the smallest absent value. ($\Rightarrow$) Conversely, if some subarray $[l^{\prime },r^{\prime }]$ has mex exactly $m$, then $[l^{\prime },r^{\prime }]$ contains every value $0,\dots ,m-1$ and no occurrence of $m$ — so $[l^{\prime },r^{\prime }]$ lies entirely within one maximal $m$-avoiding segment (the one containing it, since it has no $m$ inside), and that larger maximal segment, containing $[l^{\prime },r^{\prime }]$ as a subset, also contains all of $0,\dots ,m-1$. So the criterion is exactly “some maximal $m$-avoiding segment contains $0,\dots ,m-1$”. Sweeping and checking each gap exactly when its closing occurrence of $m$ is reached (so the gap’s full extent is known) and the “min of last positions over $[0,m)$” tree is up to date for that extent, correctly evaluates the criterion online in $O(n\log n)$ total (summing over the $O(n)$ values of $m$ with $O(\log n)$ work each via the tree descent). $■$

Counting and summing mex over all subarrays:

• Fix the left end $l$ and track $f(r)$ = mex of $a[l..r]$, which is non-decreasing in $r$. Compute $f$ for $l=0$ in one pass.
• Moving $l$ to $l+1$ deletes $a_l$: for $r$ before the next occurrence of $a_l$, the new value is $\min (f(r),a_l)$. Since $f$ is monotone, that’s a range assign on a suffix of that interval, found by binary search on the segment tree. Summing $f$ after each step gives the sum of mexes over all subarrays in $O(n\log n)$.

Proof: $f(r)$ is non-decreasing, and the deletion update is correct

Monotonicity: $a[l..r+1]\supseteq a[l..r]$ as a multiset of distinct values present, so every value present in $a[l..r]$ is still present in $a[l..r+1]$; the mex (smallest absent value) can only increase or stay the same as the set of present values grows. Deletion update: removing $a_l$ when moving to $l+1$ can only affect $f(r)$ for $r$ in the window before $a_l$‘s next occurrence (call it $r^{\prime }-1$, where $r^{\prime }$ is that next occurrence) — for $r\ge r^{\prime }$, $a_l$ still occurs again within $[l+1,r]$, so its presence is unaffected and $f(r)$ is unchanged. For $r<r^{\prime }$, $a_l$ is now completely absent from $[l+1,r]$ where it used to be present (at position $l$). If the old mex $f(r)\le a_l$, removing $a_l$ changes nothing ($a_l$ wasn’t the thing determining the mex, since values below it were already the bottleneck or $a_l$ itself wasn’t yet “needed”). If $f(r)>a_l$, then $a_l<f(r)$ means $a_l$ was one of the values $0,\dots ,f(r)-1$ that were all present; removing it makes $a_l$ now absent, so the new mex becomes exactly $a_l$ (every value below $a_l$ is still present, unaffected by removing $a_l$, and $a_l$ itself is now the smallest absent value). Combining both cases: the new value is $\min (f(r),a_l)$. Since $f$ is non-decreasing in $r$, the set of $r$ with $f(r)>a_l$ (where the update actually changes something, assigning them to $a_l$) is a contiguous suffix of the window $[l+1,r^{\prime }-1]$, found by binary searching for the first $r$ with $f(r)>a_l$. $■$

• Alternatively, $\sum \text{mex}={\sum }_{v\ge 0}\#\{\text{subarrays containing all of }\mathrm{0..}v\}$. For a permutation each count is a rectangle determined by the span of the positions of $\mathrm{0..}v$, so the whole sum is $O(n)$.

Proof: $\sum \text{mex}={\sum }_{v\ge 0}\#\{\text{subarrays containing all of }\mathrm{0..}v\}$, and the permutation rectangle count

The mex of a subarray is $m$ means it contains $0,\dots ,m-1$ but not $m$, so $\text{mex}={\sum }_{v=0}^{m-1}1={\sum }_{v\ge 0}[\text{subarray contains all of }\mathrm{0..}v]$ (summing the indicator for $v=0,\dots ,m-1$ gives $m$, and for $v\ge m$ the indicator is $0$ since $v=m$ itself, hence everything after, is missing $m$ or possibly more). Summing over all subarrays and swapping the order of summation gives ${\sum }_{\text{subarrays}}\text{mex}={\sum }_{v\ge 0}\#\{\text{subarrays containing all of }\mathrm{0..}v\}$. For a permutation of $0,\dots ,n-1$, each value has a unique position, so “containing all of $0,\dots ,v$” means the subarray’s range $[l,r]$ satisfies $l\le \min (\text{pos}(0),\dots ,\text{pos}(v))$ and $r\ge \max (\text{pos}(0),\dots ,\text{pos}(v))$ — a rectangle of valid $(l,r)$ pairs of size $({\min }_v+1)\times (n-{\max }_v)$ where ${\min }_v,{\max }_v$ are the min/max positions of $\mathrm{0..}v$, computable incrementally in $O(1)$ per $v$ by maintaining a running min/max as $v$ increases, giving $O(n)$ total. $■$

Mex of a set as a game value: Grundy numbers are mexes; see Sprague-Grundy.

Mex with permutations: in a permutation of $\mathrm{0..}n-1$, the mex of a subarray is $k$ iff the subarray contains positions of $\mathrm{0..}k-1$ and not the position of $k$. Fixing $k$ gives a rectangle of valid $(l,r)$, counted in $O(1)$, so all-subarray statistics on permutations are $O(n)$.