ABC-392-F - Insert（树状数组找第K个空位） · znzryb

## 思路讲解

![image](https://media.znzryb.com/20250210-602adac7/image_fafd7d82.png)

倒过来找，不断的找树状数组上第pi个空位

这样做是对的原因是前面的被占的都是后来者，你是先来的，所以你只用管空白位置，完全不用管被占的位置

## AC代码

AC

[https://atcoder.jp/contests/abc392/submissions/62634320](https://atcoder.jp/contests/abc392/submissions/62634320)

```cpp
// Problem: F - Insert
// Contest: AtCoder - Japan Registry Services (JPRS) Programming Contest 2025#1
// (AtCoder Beginner Contest 392) URL:
// https://atcoder.jp/contests/abc392/tasks/abc392_f Memory Limit: 1024 MB Time
// Limit: 2000 ms by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(5e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T, P[MAXN], ans[MAXN];

struct BIT {  // 普通的单点修改区间查询树状数组（依赖MAXN）
  ll tr[MAXN];
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    FOR(i, 1, n) { tr[i] = 0; }
  }
  inline void add(int p, int x) {
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx+1;	// 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};

inline void solve() {
  cin >> N;
  BIT cnt(N);
  FOR(i, 1, N) { cin >> P[i]; }
  ROF(i, N, 1) {
    ll p = cnt.findKth(P[i]);  // 所有之后要在P[i]之前的都会影响i的摆放
    ans[p] = i;
    cnt.add(p, 1);
  }
  FOR(i, 1, N) { cout << ans[i] << ' '; }
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();

  return 0;
}
/*
AC
https://atcoder.jp/contests/abc392/submissions/62634320
9
1 2 2 4 5 2 3 2 3

1 8 9 6 7 3 2 4 5

*/
```

## 心路历程（WA，TLE，MLE……）