Revival

All the $\texttt{p}$ positions are fixed; all the $\texttt{s}$ positions are unknown and need to be filled. So, sweeping left to right: for each $\texttt{s}$ position, try to place the smallest available number that doesn't produce a contradiction (make some later $\texttt{s}$ constraint impossible, drive an inversion count negative, and so on).

I couldn't make it work. The trouble is that a choice at one $\texttt{s}$ position changes the inversion count of every later prefix — each subsequent $\texttt{s}$ constraint has to be re-checked against every placement made so far, and I couldn't find an invariant (or a working swap argument) that kept the bookkeeping consistent.

Two observations worth salvaging before moving on:

If you look at the first $\texttt{s}$ position, there is a particular interval of numbers that could legally go there — too large a number creates too many inversions, too small creates too few. So: what if, after every $\texttt{s}$ position, we maintain for each open position the interval of numbers it could still hold?

As we proceed, each new $\texttt{s}$ constraint forces us to tighten earlier intervals — later prefix constraints imply things about earlier choices — so we keep intersecting intervals as we go.

I wasn't able to find a clean way to fix up the intervals: handling the overlapping intersections, and the fact that every new $\texttt{s}$ position can invalidate every earlier interval, got away from me. The same disease as Idea 1: going left-to-right means every new constraint reaches backward over everything already placed.

An aside: I gave myself one hour to solve this problem, and my brain got stuck here making no progress. (See the Learning points.)

Ideas 1 and 2 kept dying the same death: each $\texttt{s}$ position contains information about all previous positions, so sweeping left-to-right means every new $\texttt{s}$ constraint forces an update of everything before it. There is an inherent asymmetry here.

The proof is two lemmas.

Since the input demands that this total equal $x_i$ exactly, each candidate $v$ either hits $x_i$ or doesn't. Uniqueness comes from:

So the choice of $v$ is unique — and better: since the inversion total is strictly decreasing in $v$, we can binary search for it among the available values.

But how do we evaluate a candidate $v$ quickly — how do we count the prefix inversions?

Assume a RankedSet data structure with these operations (all $O(\log n)$; see the Aside for the Segment Tree implementation):

insert(v)      -> add v to the set
remove(v)      -> remove v from the set
size()         -> number of items in the set
rank(v)        -> number of items strictly below v
nth(r)         -> the item with rank r (r-th smallest)
inversions(v)  -> number of items greater than v  ( = size() - rank(v) - 1, for v in the set)

The overall solution, sweeping the $\texttt{s}$ positions from right to left. Conceptually it is very short:

S = RankedSet containing 1..n            # values not yet placed
 
for each 's' position i, from rightmost to leftmost:
    remove from S the values at 'p' positions right of i (not already removed)
 
    # INV(v) := number of inversions in prefix P[1..i] if v goes at position i
    #   - computable for any candidate v   (Lemma 1)
    #   - strictly decreasing in v         (Lemma 2)
    binary search the candidates in S (by rank) for the v with INV(v) == x[i]
 
    P[i] = v ; S.remove(v)

Making the accounting exact. All the real work hides inside evaluating $\text{INV}(v)$, and three tricks are needed to get it right and fast:

1. Evaluate $\text{INV}(v)$ through the previous $\texttt{s}$ position. Following Lemma 1's classification: $\text{INV}(v) = x_{i_2} + (\text{block inversions}) + (\text{inversions contributed by } v)$, where $i_2$ is the previous $\texttt{s}$ position and the block is the run of $\texttt{p}$ positions between $i_2$ and $i$. The first term is free (it's input), and the last is a single query: values greater than $v$ among those that will sit to its left.
2. Charge each block once. The block contribution is (almost) independent of the candidate $v$, so compute it once per block — each block value $b$ contributes the count of still-unplaced values greater than $b$ — instead of re-summing it every time the binary search tests a candidate. Without this, long blocks blow up the complexity.
3. Correct for the candidate itself. When the block sums were computed, the candidate $v$ was still among the unplaced values — so each block value $b$ counted $v$ as if it were to the block's left, but $v$ actually lands to the block's right, where the pair inverts only if $b > v$. Each time the binary search tests a candidate $v$, both directions are fixed in one stroke: subtract the block values below $v$, add the block values above $v$ (keep the block in its own small RankedSet to answer these).

The same pseudocode with the accounting written out:

S = RankedSet containing 1..n            # values not yet placed
remove from S every value at a 'p' position right of the last 's' position
treat position 0 as a virtual 's' with x[0] = 0   # handles the leftmost block
 
for each 's' position i, from rightmost to leftmost:
    let i2    = the previous 's' position (or the virtual position 0)
    let block = the 'p' positions strictly between i2 and i
 
    # trick 2: block contribution, computed ONCE per block
    #   for each block value b (right to left): count values still in S
    #   greater than b, then move b from S into a small RankedSet B
    base = x[i2] + sum of block contributions
 
    # binary search over the remaining candidates in S (by rank):
    #   INV(v) = base + B.inversions-above(v) - B.count-below(v)   # trick 3
    #                 + (items of S other than v that are greater than v)
    binary search the rank r such that v = S.nth(r) gives INV(v) == x[i]
 
    P[i] = v ; S.remove(v)

Each $\texttt{s}$ position costs $O(\log^2 n)$ (a binary search where each candidate test is a few $O(\log n)$ set queries), each $\texttt{p}$ value is inserted and removed a constant number of times, so the whole thing runs in $O(n \log^2 n)$.

Watch the edge cases: a run of $\texttt{p}$ positions at the very end (strip them before the first iteration), a run at the very beginning (the virtual $\texttt{s}$ at position 0 absorbs it), and two adjacent $\texttt{s}$ positions (an empty block).

A Segment Tree handles a fixed universe of items $1..n$ with point updates + range queries (or the reverse) over any associative operation — sums, mins, maxes. It's also useful for problems that don't look like range queries at all: here, we "add 1" at position $v$ when $v$ enters the set and "subtract 1" when it leaves, so the tree maintains counts, and a range query counts how many set members are $\leq$ some value.

The core idea: a binary tree whose leaves are the universe items, where each internal node stores the sum of its children. To keep the arithmetic trivial, every call carries the range $(a,b)$ it covers and the node index $i$: the root is node $0$ covering $(1,n)$; node $i$'s children are $2i+1$ (left) and $2i+2$ (right); the split point is $m = \lfloor (a+b)/2 \rfloor$, with the left child covering $(a,m)$ and the right $(m+1,b)$; you're at a leaf when $a = b$. The splits come out slightly lopsided, but the depth is still $O(\log n)$ and the whole thing is very easy to write from memory.

The RankedSet used above, as a segment tree over counts (pseudocode distilled from my accepted C++):

D = [0] * (4 * n)                 # D[i] = number of set members in node i's range
 
def insert(v, a=1, b=n, i=0):     # add 1 at leaf v, fix sums on the way up
    if b < v or a > v: return
    if a == b: D[i] += 1; return
    m = (a + b) // 2
    insert(v, a, m, 2*i+1); insert(v, m+1, b, 2*i+2)
    D[i] = D[2*i+1] + D[2*i+2]
 
def remove(v, a=1, b=n, i=0):     # identical, with D[i] -= 1 at the leaf
    ...
 
def size(): return D[0]
 
def rank(v, a=1, b=n, i=0):       # how many members are strictly below v
    if a == b: return 0
    m = (a + b) // 2
    if v <= m: return rank(v, a, m, 2*i+1)
    return D[2*i+1] + rank(v, m+1, b, 2*i+2)
 
def nth(r, a=1, b=n, i=0):        # the member with rank r
    if a == b: return a
    m = (a + b) // 2
    if D[2*i+1] > r: return nth(r, a, m, 2*i+1)
    return nth(r - D[2*i+1], m+1, b, 2*i+2)
 
def inversions(v): return size() - rank(v) - 1    # members greater than v (v in set)