Overview

In this problem, we are given a sequence of cards to stack according to specific rules. Our goal is to minimize the final “number of piles” while maximizing the sum of the indices representing the stacking relationships, \(\sum B_i\).

By viewing the stacking relationships as a “matching,” we can solve this problem efficiently in \(O(N \log N)\) time by combining a greedy approach with binary search (std::set).

Analysis

Rephrasing the Problem (Matching)

The conditions for stacking card \(i\) on top of card \(j\) are as follows: 1. \(j < i\) (card \(j\) is placed first) 2. \(A_j \geq A_i\) (the value of the bottom card is greater than or equal to the value of the top card)

Let us represent placing card \(i\) directly on top of card \(j\) as a directed edge \(j \to i\). Each card can be “placed under another card (become a parent)” at most once, and “stacked on top of another card (become a child)” at most once.

If we denote the total number of stacked cards (the size of the matching) as \(M\), the final number of piles will be \(N - M\). Therefore, minimizing the number of piles is equivalent to maximizing the matching size \(M\).

Furthermore, we are required to maximize the sum of the indices of the cards directly underneath, \(\sum B_i\). This is equivalent to maximizing the sum of the parent indices \(j\) selected in the matching.

Designing the Greedy Algorithm

To minimize the number of piles (maximize \(M\)) while maximizing the sum of the parent indices \(j\), we can use a greedy approach where we decide whether card \(j\) can be used as a “parent” in the matching, starting from the largest index (the rightmost card) and moving leftwards.

We iterate \(j\) in reverse order from \(N\) down to \(1\). For a fixed \(j\), the candidates that can be stacked on top (children) are the unassigned cards \(i\) such that \(j < i\). Among these candidates, which \(i\) satisfying \(A_i \leq A_j\) should we choose?

Here, it is optimal to “choose the \(i\) with the maximum \(A_i\) among those satisfying \(A_i \leq A_j\).” The reason is as follows: - Cards with smaller \(A_i\) have a wider range of potential matches for smaller \(j' (< j)\) that we will process later, so we want to save them. - Therefore, consuming the largest possible \(A_i\) that is just barely within the limit of the current \(A_j\) is the smartest choice, as it leaves the maximum flexibility for future matchings.

Additionally, by scanning \(j\) from largest to smallest (\(N\) down to \(1\)) and establishing a match immediately whenever possible, larger indices \(j\) are preferentially chosen as the values for \(B_i\), which automatically maximizes \(\sum B_i\).

Algorithm

Specifically, the process is carried out as follows:

1. Preparation of Data Structures:

   • Prepare a set s of cards that have not yet been used as a “child” in any matching. This will be a balanced binary search tree (C++ std::set) managing pairs of value and index, (A[i], i).
   • Initialize the array B with \(0\).

2. Reverse Loop:

   • Loop through \(j\) decrementing from \(N\) down to \(1\).
   • In each step of the loop for \(j\):
     1. If \(j < N\), card \(j+1\) becomes available as a candidate “child”, so insert (A[j+1], j+1) into s.
     2. Find the element in s with the maximum \(A_i\) satisfying \(A_i \leq A_j\) using binary search (upper_bound).
     3. If a matching element \(i\) is found:
        • Set \(B_i = j\).
        • Remove the element \(i\) from s (since a card can only be stacked once).
        • Increment the matching size \(M\) by 1.

3. Output:

   • Output the minimum number of piles, \(K = N - M\).
   • Output the array \(B_1, \ldots, B_N\).

Simulation with a Concrete Example

Consider the case where \(N = 4\) and \(A = [4, 2, 3, 1]\).

• \(j = 4\) (\(A_4 = 1\)):
  • s is empty. No matching.
• \(j = 3\) (\(A_3 = 3\)):
  • Add (A_4, 4) = (1, 4) to s. s = {(1, 4)}.
  • The maximum element satisfying \(A_i \leq A_3 (3)\) is \(A_4 = 1\).
  • Set \(B_4 = 3\) and remove it from s. s = {}, \(M = 1\).
• \(j = 2\) (\(A_2 = 2\)):
  • Add (A_3, 3) = (3, 3) to s. s = {(3, 3)}.
  • No element in s satisfies \(A_i \leq A_2 (2)\) (since \(3 > 2\)). No matching.
• \(j = 1\) (\(A_1 = 4\)):
  • Add (A_2, 2) = (2, 2) to s. s = {(2, 2), (3, 3)}.
  • The maximum element satisfying \(A_i \leq A_1 (4)\) is \(A_3 = 3\).
  • Set \(B_3 = 1\) and remove it from s. s = {(2, 2)}, \(M = 2\).

Result: - Number of piles \(K = 4 - 2 = 2\) - \(B = [0, 0, 1, 3]\) (This corresponds to Pile 1: \(1 \to 3 \to 4\), Pile 2: \(2\), which indeed satisfies the conditions)

Complexity

• Time Complexity: \(O(N \log N)\)
  • The loop for \(j\) runs \(N\) times.
  • Inside each loop, insertion (insert), binary search (upper_bound), and deletion (erase) on std::set can all be performed in \(O(\log N)\) time.
  • Therefore, the total time complexity is \(O(N \log N)\), which easily passes within the time limit under the constraint \(N \leq 2 \times 10^5\).
• Space Complexity: \(O(N)\)
  • Since the sizes of the arrays \(A, B\) and the std::set are at most \(N\), the space complexity is \(O(N)\).

Key Implementation Points

• Binary Search on std::set:

  • To find the largest element satisfying A[i] <= A[j], we can use s.upper_bound({A[j], N + 1}).
  • upper_bound returns an iterator pointing to the first element that is strictly greater than the given value. Therefore, by decrementing the obtained iterator by one (--it), we can point to the largest element satisfying A[i] <= A[j].
  • If the iterator points to s.begin(), it means no element satisfies the condition, so we must skip it safely.

• Comparison Order of Pairs:

  • A std::set<pair<int, int>> is compared primarily by its first element (the value \(A_i\) written on the card), and then by its second element (the index \(i\)) in case of ties. This ensures that the binary search based on values works correctly.

    Source Code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

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

    vector<int> B(N + 1, 0);
    // 利用可能なカード i を {A[i], i} のペアで管理する
    set<pair<int, int>> s;
    int M = 0; // マッチング数（重ねられたカードの数）

    // 右側のカードから順にマッチングの親（下になるカード）として選べるか走査する
    for (int j = N; j >= 1; --j) {
        // j より右側にあるカード j + 1 が新たに利用可能になる
        if (j < N) {
            s.insert({A[j + 1], j + 1});
        }
        
        // A[i] <= A[j] を満たす最大の A[i] を持つ要素を二分探索
        auto it = s.upper_bound({A[j], N + 1});
        if (it != s.begin()) {
            --it; // 条件を満たす最大の要素を指すようにデクリメント
            int i = it->second;
            B[i] = j;      // カード i の直下のカードを j に設定
            s.erase(it);   // 使用したカードを候補から削除
            M++;
        }
    }

    // 山の数の最小値 K = N - (重ねられたカードの数)
    cout << N - M << "\n";
    for (int i = 1; i <= N; ++i) {
        cout << B[i] << (i == N ? "" : " ");
    }
    cout << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.