xiv. Permutation Tree

For a permutation $p$, call a subarray $p[l..r)$ an interval if its values form a contiguous range, i.e. $\max -\min =r-l-1$. The permutation tree (also called the cut/join tree) encodes all $O(n^2)$ intervals in $O(n)$ nodes. Problems: count intervals (CF 526F), count intervals inside a query range (CF 997E), shortest interval containing given positions (gym 101620 I), count permutations with no nontrivial interval (simple permutations).

Counting intervals without the tree

For a fixed right end $r$ (exclusive), let $f(l)=\max p[l..r)-\min p[l..r)-(r-1-l)$. Then $f(l)\ge 0$, with equality iff $p[l..r)$ is an interval. Keep $f$ in a segment tree with range add and “min + count of min”:

• moving $r$ forward subtracts 1 from every $f(l)$, $l<r$ (the length term) and sets $f(r-1)=0$;
• the max term changes on a contiguous block of $l$ per popped element of a monotonic max-stack; do a range add of the difference. Same for the min-stack.

The number of intervals ending at $r$ is the number of zeros among $f(\mathrm{0..}r-1)$, which is the count of the minimum when the minimum is 0. Total $O(n\log n)$.

// seg: range add, query (min, count of min) over [0, n)
ll countIntervals(const vector<int>& p) {
    int n = sz(p); ll ans = 0; vector<int> mx, mn;              // stacks of indices
    for (int r = 0; r < n; r++) {
        while (sz(mx) && p[mx.back()] < p[r]) { int j = mx.back(); mx.pop_back(); seg.add(sz(mx) ? mx.back() + 1 : 0, j + 1, p[r] - p[j]); }
        mx.push_back(r);
        while (sz(mn) && p[mn.back()] > p[r]) { int j = mn.back(); mn.pop_back(); seg.add(sz(mn) ? mn.back() + 1 : 0, j + 1, p[j] - p[r]); }
        mn.push_back(r);
        if (r) seg.add(0, r, -1);                                // the length term grew by one
        auto [m, c] = seg.query(0, r + 1);
        ans += m == 0 ? c : 0;
    }
    return ans;
}

For “number of intervals inside $[L,R)$” (CF 997E), add a lazy tag “add the current zero-count to a per-node historic counter” and apply it to the whole prefix after every step; then answer queries with right end $R$ by a range query of historic counts over $[L,R)$.

Proof: $f(l)\ge 0$ with equality exactly on intervals

$p[l..r)$ has $r-l$ distinct integers between its min and max, so $\max -\min +1\ge r-l$, which is $f(l)\ge 0$. Equality means the $r-l$ distinct values fill the whole range $[\min ,\max ]$, which is the definition of an interval. When $r$ increases, the max over $[l,r]$ changes only for the $l$ between the new element and the previous greater element, and on each popped stack block the old max was the popped value, so adding $p_r-p_j$ on that block updates the term exactly; similarly for the min.

Structure

Two intervals overlap if they intersect and neither contains the other.

Lemma: if intervals $A$ and $B$ overlap, then $A\cap B$, $A\cup B$, $A\setminus B$ and $B\setminus A$ are intervals

As position ranges, $A\cap B$ and $A\cup B$ are contiguous. Their value sets: $\text{val}(A)$ and $\text{val}(B)$ are integer ranges that intersect (they share the values at the positions of $A\cap B$), so $\text{val}(A)\cup \text{val}(B)=\text{val}(A\cup B)$ is an integer range and $A\cup B$ is an interval. $\text{val}(A\cap B)=\text{val}(A)\cap \text{val}(B)$, an intersection of ranges, so $A\cap B$ is an interval. $A\setminus B$ is contiguous in positions (since neither contains the other) and its values are $\text{val}(A)\setminus \text{val}(B)$, a range minus a range that is not strictly inside it (otherwise $\text{val}(A\cup B)=\text{val}(A)$ would have size $<|A\cup B|$), hence a range.

An interval is strong if no interval overlaps it. Strong intervals form a laminar family (any two are nested or disjoint), so they form a tree: the root is $[0,n)$, the leaves are single positions, and the children of a node are its maximal strong proper subintervals, which partition it. Read the children’s value blocks in order; their relative order (the quotient permutation) is either

• monotone (a join node, increasing or decreasing): every union of consecutive children is an interval; or
• simple (a cut/prime node): no union of $2\le j<k$ consecutive children is an interval. A simple permutation has $k\ge 4$ (none exist for $k=3$).

Every interval is either a node or a union of $\ge 2$ consecutive children of a join node. So the number of intervals is

$\#\text{nodes}+{\sum }_{\text{join }u}\left(\left(\genfrac{}{}{0ex}{}{k_u}{2}\right)-1\right).$

Proof: the classification

Let $I$ be an interval and $S$ the smallest strong interval containing it. Every child $C$ of $S$ is strong, so it doesn’t overlap $I$: either $C\subseteq I$, $C\cap I=\varnothing$, or $I⊊C$, and the last contradicts the minimality of $S$. So $I$ is a union of consecutive children.

Now the quotient of $S$ (sketch; this is the substitution decomposition theorem of Albert and Atkinson). If some union $U$ of $2\le j<k$ consecutive children is an interval, it is not strong (it would lie strictly between $S$ and its children, contradicting their maximality), so some interval $J$ overlaps it; $J⊊S$ because $S$ is strong, so $J$ is also a union of children. Take $U$ maximal: by the lemma $U\cup J$ is a strictly larger interval, so $U\cup J=S$. Thus $S$ splits into consecutive blocks $A=U\setminus J$, $B=U\cap J$, $C=J\setminus U$, all intervals, with $A\cup B$ and $B\cup C$ intervals, so their values are monotone (say $A<B<C$). Repeating the argument on the maximal proper prefix interval and suffix interval shows that every boundary between consecutive children separates smaller values from larger ones in the same direction, so the quotient is the identity or its reverse. Hence either the quotient has no nontrivial interval (cut node: then $I=S$ or $I$ is a single child, both nodes), or it is monotone (join node: every consecutive union is an interval).

Counting: each node is one interval; a join node with $k$ children additionally contributes the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)-1$ consecutive unions of at least 2 but not all children.

$O(n\log n)$ construction

Sweep $r$ with the $f$-segment tree above and a stack of nodes whose position ranges tile $[0,r)$. When a new leaf arrives, repeatedly:

1. if the top of the stack is a join node whose last child is adjacent in value to the current node in the same direction, append the current node as its child;
2. else if the top and the current node are adjacent in value, create a new join node with these two children;
3. else if the segment tree says some $l$ to the left gives an interval ending here (min of $f$ over $[0,\text{start of current})$ is 0), pop nodes until their union is an interval and make them children of a new cut node;
4. otherwise stop and push the current node.

struct PermutationTree {                             // p: permutation of 0..n-1
    int n, root = -1, cnt = 0, LOG = 1;
    vector<vector<int>> ch;                          // children ordered by position; leaves are nodes 0..n-1
    vector<int> type, lo, hi, vlo, vhi, par;         // type 0 leaf/cut, 1 increasing join, 2 decreasing join; [lo, hi), [vlo, vhi)
    vector<vector<int>> up; vector<int> mn, lz;
    void app(int p, int v) { mn[p] += v, lz[p] += v; }
    void push(int p) { if (lz[p]) app(2 * p, lz[p]), app(2 * p + 1, lz[p]), lz[p] = 0; }
    void update(int p, int b, int e, int l, int r, int v) {   // closed ranges, 1-indexed
        if (r < b || e < l || l > r) return;
        if (l <= b && e <= r) return app(p, v);
        push(p); int m = (b + e) / 2;
        update(2 * p, b, m, l, r, v); update(2 * p + 1, m + 1, e, l, r, v);
        mn[p] = min(mn[2 * p], mn[2 * p + 1]);
    }
    int query(int p, int b, int e, int l, int r) {
        if (r < b || e < l || l > r) return INT_MAX;
        if (l <= b && e <= r) return mn[p];
        push(p); int m = (b + e) / 2;
        return min(query(2 * p, b, m, l, r), query(2 * p + 1, m + 1, e, l, r));
    }
    PermutationTree(const vector<int>& perm) : n(sz(perm)) {
        if (!n) return;
        int N = 2 * n + 2; vector<int> p(n + 1);
        for (int i = 0; i < n; i++) p[i + 1] = perm[i] + 1;
        vector<vector<int>> g(N); vector<int> ty(N), pa(N, -1), rl(N), rr(N), sl(N), sr(N);
        mn.assign(4 * n + 4, 0), lz.assign(4 * n + 4, 0);
        auto addEdge = [&](int u, int v) { pa[v] = u, g[u].push_back(v); };
        auto adj = [&](int i, int j) { return rr[i] == rl[j] - 1; };
        auto len = [&](int i) { return rr[i] - rl[i] + 1; };
        int id = n + 1; vector<int> mx = {0}, mi = {0}, st;
        for (int i = 1; i <= n; i++) {
            while (mx.back() && p[mx.back()] < p[i]) { int r = mx.back(); mx.pop_back(); update(1, 1, n, mx.back() + 1, r, p[i] - p[r]); }
            mx.push_back(i);
            while (mi.back() && p[mi.back()] > p[i]) { int r = mi.back(); mi.pop_back(); update(1, 1, n, mi.back() + 1, r, p[r] - p[i]); }
            mi.push_back(i);
            rl[i] = rr[i] = p[i]; sl[i] = sr[i] = i;
            int cur = i;
            while (true) {
                if (sz(st) && (adj(st.back(), cur) || adj(cur, st.back()))) {
                    int b = st.back();
                    if ((adj(b, cur) && ty[b] == 1) || (adj(cur, b) && ty[b] == 2)) {
                        addEdge(b, cur);
                        rl[b] = min(rl[b], rl[cur]), rr[b] = max(rr[b], rr[cur]), sl[b] = min(sl[b], sl[cur]), sr[b] = max(sr[b], sr[cur]);
                        cur = b; st.pop_back();
                    } else {
                        ty[id] = adj(b, cur) ? 1 : 2; addEdge(id, b); addEdge(id, cur);
                        rl[id] = min(rl[b], rl[cur]), rr[id] = max(rr[b], rr[cur]), sl[id] = min(sl[b], sl[cur]), sr[id] = max(sr[b], sr[cur]);
                        st.pop_back(); cur = id++;
                    }
                } else if (query(1, 1, n, 1, i - len(cur)) == 0) {
                    int L = len(cur), a = rl[cur], b = rr[cur], s1 = sl[cur], s2 = sr[cur];
                    addEdge(id, cur);
                    do {
                        int t = st.back(); L += len(t);
                        a = min(a, rl[t]), b = max(b, rr[t]), s1 = min(s1, sl[t]), s2 = max(s2, sr[t]);
                        addEdge(id, t); st.pop_back();
                    } while (b - a + 1 != L);
                    reverse(all(g[id]));
                    rl[id] = a, rr[id] = b, sl[id] = s1, sr[id] = s2; cur = id++;
                } else break;
            }
            st.push_back(cur);
            update(1, 1, n, 1, i, -1);
        }
        cnt = id - 1;
        ch.assign(cnt, {}), type.assign(cnt, 0), lo.assign(cnt, 0), hi.assign(cnt, 0), vlo.assign(cnt, 0), vhi.assign(cnt, 0), par.assign(cnt, -1);
        for (int u = 1; u <= cnt; u++) {
            int x = u - 1;
            for (int v : g[u]) ch[x].push_back(v - 1);
            type[x] = ty[u]; lo[x] = sl[u] - 1, hi[x] = sr[u]; vlo[x] = rl[u] - 1, vhi[x] = rr[u];
            par[x] = pa[u] == -1 ? -1 : pa[u] - 1;
            if (pa[u] == -1) root = x;
        }
        while ((1 << LOG) < cnt) LOG++;
        up.assign(LOG, vector<int>(cnt));
        for (int u = 0; u < cnt; u++) up[0][u] = par[u] == -1 ? u : par[u];
        for (int k = 1; k < LOG; k++) for (int u = 0; u < cnt; u++) up[k][u] = up[k - 1][up[k - 1][u]];
    }
    pair<int, int> minimalInterval(int l, int r) const {     // shortest interval containing positions [l, r)
        if (r - l == 1) return {l, r};
        int u = l;
        for (int k = LOG - 1; k >= 0; k--) if (hi[up[k][u]] < r) u = up[k][u];
        u = par[u];
        if (type[u] == 0) return {lo[u], hi[u]};
        const auto& c = ch[u];
        int a = *partition_point(all(c), [&](int v) { return hi[v] <= l; });
        int b = *(partition_point(all(c), [&](int v) { return lo[v] < r; }) - 1);
        return {lo[a], hi[b]};
    }
    ll countIntervals() const {
        ll t = 0;
        for (int u = 0; u < cnt; u++) { t++; if (type[u]) { ll k = sz(ch[u]); t += k * (k - 1) / 2 - 1; } }
        return t;
    }
};

Proof: the construction is $O(n\log n)$ and builds the tree

Each step of the inner loop either attaches a node to an existing join node, creates a new node, or stops. Nodes are created at most $n-1$ times and each node is popped from the stack at most once, so the loop runs $O(n)$ times in total, each with $O(\log n)$ segment tree work; the stacks for max/min add $O(n)$ range updates. The stack invariant is that its nodes tile $[0,r)$ and no union of a suffix of them with the current node is an interval unless detected: the segment tree query over left endpoints before the current node’s start detects exactly that some suffix union ending at $r$ is an interval. A suffix union that is an interval either has two members adjacent in value (handled as join) or needs at least four members whose union first becomes an interval at a cut node, which is why the cut case pops until the value range has no gaps. The resulting nodes are exactly the strong intervals, matching the structure above.

Uses

• Minimal interval containing positions $[l,r)$: lift from leaf $l$ to the deepest ancestor not containing $r-1$, take its parent $u$; if $u$ is a cut node the answer is $u$, otherwise the union of $u$‘s children from the one containing $l$ to the one containing $r-1$. $O(\log n)$.
• Counting simple permutations / permutations by interval structure: decompose by the root type; the generating function of simple permutations satisfies a functional equation with the one of all permutations.
• “Sort by reversing intervals” and “split into maximum number of interval pieces”: DP over the tree; a join node’s children can be grouped freely.
• Interval-based DP on permutations (“number of subarrays that are intervals and satisfy X”): iterate over nodes, handling join nodes’ consecutive unions in $O(k)$ or $O(k\log k)$.