กำหนดให้ $A_i$ แทนหมายเลขของนักกล้ามที่เดินเข้ายิมเป็นคนที่ $i$ และ $p_i$ คือจำนวนที่นักกล้ามตะโกนขณะที่นักกล้ามคนที่ $i$ กำลังเดินเข้ามาในยิม

กำหนดให้ฟังก์ชั่น $L(S, x)$ เท่ากับจำนวนสมาชิกในเซต $S$ ที่มีค่าน้อยกว่าจำนวนเต็ม $x$

ในข้อนี้ เราจะต้องหาลำดับของหมายเลขนักกล้ามที่เดินเข้ามาในยิม จากข้อมูลที่นักกล้ามแต่ละคนตะโกนเมื่อเดินเข้ายิม

หากนักกล้ามคนที่ $1$ ถึง $n - 1$ ได้เดินเข้ามาในยิมเป็นที่เรียบร้อยแล้ว กำหนดให้ $S_i$ เป็นเซตของหมายเลขของนักกล้ามที่อยู่ในยิมแล้ว $i$ คนแรก จะได้ว่า $S_n$ เป็น $\{1, 2, ..., A_n - 1, A_n, A_n + 1, ..., n\}$ และ $p_n = |S_n| - L(S_n, A_n) - 1$ สังเกตว่า $|S_i| = i$ และในกรณีนี้ $L(S_n, A_n) = A_n - 1$ เสมอ ดังนั้นจึงสรุปได้ว่า $p_n = n - A_n$ หรือ $A_n = n - p_n$ นั่นเอง

เมื่อเราทราบ $A_n, A_{n-1}, ..., A_{i + 1}$ เป็นที่เรียบร้อยแล้ว จะได้ว่า $S_i = S_n - \{A_n, A_{n-1}, ..., A_{i + 1}\}$ และ $p_i = |S_i| - L(S_i, A_i) - 1$ หรือ $i - L(S_i, A_i) - 1$ ดังนั้น $L(S_i, A_i) = i - p_i - 1$

จากข้อสรุปด้านบน $A_i$ จึงเป็นจำนวนเต็ม $k$ ที่ทำให้ $L(S_i, k) = i - p_i - 1$ คุณสมบัติอย่างหนึ่งที่สามารถสังเกตได้ของฟังก์ชั่น $L(S, x)$ คือ $L(S_i, a) \leq L(S_i, b)$ เมื่อ $a < b$ ดังนั้น เราจึงสามารถใช้การ Binary Search เพื่อหา $A_i$ ได้

สำหรับการหา $L(S, x)$ เราจะใช้ Fenwick Tree โดยกำหนดให้ $t_i$ คือค่าของ Fenwick Tree ช่องที่ $i \,$ Fenwick Tree ประกอบไปด้วยสอง operation ได้แก่ update(i, k) คือเพิ่มค่า $k$ ให้แก่ $t_i$ และ query(i) คือจะคืนค่า $\sum \limits_{j=1}^{i} t_j$ โดยทั้งสอง operation ใช้เวลา $\mathcal{O}(\log N)$ ต่อการเรียก 1 ครั้ง

นิยามให้ $t_i$ จะเป็น 1 ก็ต่อเมื่อ $i \in S$ และเป็น 0 เมื่อ $i \notin S$ ดังนั้น $L(S, x) = \sum \limits_{i=1}^{x-1} t_i$ หรือ query(x - 1) ทำให้เราสามารถ Binary Search หาจำนวนเต็ม $k$ ที่น้อยที่สุดที่ $L(S, k) = i - p_i - 1$ หรือ $A-i$ นั่งเอง เมื่อทราบค่า $A_i$ แล้ว เราก็ทำการลบ $A_i$ ออกจากเซต $S$ เพื่อเปลี่ยนจาก $S_i$ เป็น $S_{i-1}$ ด้วยการกำหนดให้ $t_{A_i}$ เป็น 0

เนื่องจาก Binary Search และ operation ของ Fenwick Tree ใช้เวลา $\mathcal{O}(\log N)$ จึงทำให้การหาค่า $A_i$ แต่ละค่า ใช้เวลา $\mathcal{O}(\log^2 N)$ ซึ่งสามารถลดเวลาให้เหลือ $\mathcal{O}(\log N)$ ได้

โค้ดตัวอย่างดังนี้

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n, t[N];
int A[N], ans[N];

void update(int x, int k) {
  for (int i = x; i < N; i += i & -i)
    t[i] += k;
}
int query(int x, int ret = 0) {
  for (int i = x; i; i -= i & -i)
    ret += t[i];
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", A + i), update(i, 1);
  for (int i = n; i; i--) {
    int l = 1, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (query(mid) >= i - A[i])
        r = mid;
      else
        l = mid + 1;
    }
    ans[i] = r;
    update(r, -1);
  }
  for (int i = 1; i <= n; i++)
    printf("%d ", ans[i]);
  printf("\n");

  return 0;
}

สำหรับโค้ดด้านบนนี้จะใช้เวลา $\mathcal{O}(N \log^2 N)$

int pos = 0, x = i - A[i];
for (int j = 19; ~j; j--)
  if (pos + (1 << j) <= n && t[pos + (1 << j)] < x)
    x -= t[pos += (1 << j)];
ans[i] = pos + 1;
update(pos + 1, -1);

สำหรับโค้ดด้านบนนี้เป็นการ Binary Search บน Fenwick Tree ภายในเวลา $\mathcal{O}(\log N)$ ทำให้ใช้เวลารวมแล้วเพียง $\mathcal{O}(N \log N)$ เท่านั้น

เนื่องจาก constraint ของโจทย์มีค่าไม่มากพอ การ Binary Search ทั้งสองวิธีจึงผ่านทั้งคู่