Overview

This problem asks us to stack cards from left to right into piles such that the card values in each pile are monotonically non-increasing.
By looking at the problem in reverse, it becomes a problem of partitioning the sequence into monotonically non-decreasing subsequences. We can find the minimum number of piles and the optimal \(B_i\) using a greedy approach and a set.

Analysis

If we look at the original piles from bottom to top, the card indices increase, and their values are monotonically non-increasing.

For example, if a pile is stacked in the order of

\[{p_1 < p_2 < \cdots < p_m}\]

then we have:

\[A_{p_1} \geq A_{p_2} \geq \cdots \geq A_{p_m}\]

If we look at this from right to left—that is, in the order of cards \(N, N-1, \ldots, 1\)—the same pile appears in the order of

\[p_m, p_{m-1}, \ldots, p_1\]

and their values are:

\[A_{p_m} \leq A_{p_{m-1}} \leq \cdots \leq A_{p_1}\]

Thus, when viewed in reverse, the problem can be thought of as “partitioning the sequence into as few monotonically non-decreasing subsequences as possible.”

---

When processing in reverse, we maintain the “current bottom card” of each partial pile.

The condition to add card \(i\) to the bottom of a pile (whose current bottom card is \(j\)) is:

\[A_i \geq A_j\]

In this case, in the original order, card \(i\) is directly below card \(j\), so we have:

\[B_j = i\]

---

To minimize the number of piles, if there are existing piles where the current card \(i\) can be placed, it is optimal to place it on the pile with the maximum “current bottom value”.

The reason is that piles ending with smaller values have a higher chance of accepting even smaller cards in the future.
By using the pile with the largest possible value among those that can accept the card, we can preserve the piles with smaller values.

This is a standard greedy approach for partitioning a sequence into the minimum number of monotonically non-decreasing subsequences.

For example, suppose the values in reverse order are:

\[2, 1, 2, 1\]

If the bottom values of the piles are currently \(1\) and \(2\), and we process the next \(2\):

• If we place it on the pile with value \(2\), the bottoms remain \(1\) and \(2\).
• If we place it on the pile with value \(1\), the bottoms become \(2\) and \(2\).

In the latter case, we will not be able to place the subsequent \(1\), which may result in an extra pile.

---

Additionally, the condition to maximize \(B_1 + B_2 + \cdots + B_N\) is also satisfied by this reverse greedy strategy.

When card \(i\) is added to an existing pile in the reverse process, the \(B\) of some card becomes \(i\), which increases the sum by exactly \(i\).

In other words, it is advantageous to “add to an existing pile” using cards with indices as large as possible.

This greedy method always achieves the minimum number of piles even when considering only each suffix, i.e., cards \(t, t+1, \ldots, N\).
Therefore, the number of connections made within that range—which corresponds to the number of times we contribute to \(B\)—is also maximized.

For any set \(S\), the following holds:

\[\sum_{i \in S} i = \sum_{t=1}^{N} |\{i \in S \mid i \geq t\}|\]

Since the number of contributions is maximized for each suffix, the sum of \(B_i\) is consequently maximized as well.

Algorithm

We prepare a set<pair<long long, int>> bottoms.

This set manages the following for each partial pile:

\[\text{(current bottom card value, card index)}\]

We process the cards in reverse order, from \(N\) down to \(1\).

For each card \(i\), we perform the following steps:

1. Search in bottoms for elements with a value less than or equal to \(A_i\).
2. Choose the one with the maximum value among them.
3. If none is found, create a new pile.
4. If found, let that card be child and set: $\(B_{\text{child}} = i\)$
5. Since the bottom of that pile changes to card \(i\), update the set.

In the code, we search for the element immediately after those with values less than or equal to \(A_i\) using:

auto it = bottoms.upper_bound({A[i], numeric_limits<int>::max()});

The element immediately preceding it will be the candidate for the “maximum value less than or equal to \(A_i\)”.

Complexity

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

Implementation Notes

There may be multiple cards with the same value in \(A_i\).
Therefore, we store a pair<long long, int> containing both the value and the card index in the set:

pair<long long, int>

Also, since the condition is \(A_j \leq A_i\), we must be able to select elements with equal values.
Thus, we use:

upper_bound({A[i], INF})

to include all elements with values less than or equal to \(A_i\) as candidates.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    vector<int> B(N + 1, 0);
    set<pair<long long, int>> bottoms;

    int K = 0;

    for (int i = N; i >= 1; i--) {
        auto it = bottoms.upper_bound({A[i], numeric_limits<int>::max()});

        if (it == bottoms.begin()) {
            bottoms.insert({A[i], i});
            K++;
        } else {
            --it;
            int child = it->second;
            B[child] = i;
            bottoms.erase(it);
            bottoms.insert({A[i], i});
        }
    }

    cout << K << '\n';
    for (int i = 1; i <= N; i++) {
        if (i > 1) cout << ' ';
        cout << B[i];
    }
    cout << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.