谜一样的牛(树状数组上倍增/rope）

题意：
一个1~n的排列，给出每个数前面比它大的数的个数，试还原该排列。n<=1e5.
题解：
例如n=5,0 1 2 1 0的答案是2 4 5 3 1

我们需要一个数据结构，支持单点修改和查询指定前缀和对应的第一个位置。
一个显然的想法是树状数组+二分。
其实还可以在树状数组上倍增，这样少一个log，但是需要对树状数组的结构有更深刻的理解。

//
// Created by vv123 on 2022/8/31.
//
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int n, t[N], a[N], ans[N];
int add(int i, int x) {
    for (; i <= n; i += i & -i)
        t[i] += x;
}
int ask(int i) {
    int res = 0;
    for (; i; i -= i & -i)
        res += t[i];
    return res;
}

int getpos(int x) {
    int tot = 0, sum = 0;
    for (int i = log2(n); i >= 0; i--) {
        if (tot + (1 << i) <= n && sum + t[tot + (1 << i)] < x) {
            tot += (1 << i);
            sum += t[tot];
        }
    }
    return tot + 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) add(i, 1);
    for (int i = 2; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--) {
        ans[i] = getpos(a[i] + 1);
        add(ans[i], -1);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] <<"\n";
    }
    return 0;
}

另外使用stl rope模拟，在开启O3优化后也可以通过。感觉应该是n^1.5的，目前尚不清楚为什么在不开优化的情况下无法通过（

//
// Created by vv123 on 2022/8/31.
//
#pragma GCC optimize("Ofast")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

const int N = 2e5 + 10;
int n, ans[N];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    rope<int> r;
    r.push_back(1);
    for (int i = 2; i <= n; i++) {
        int pos; cin >> pos;
        r.insert(pos, i);
    }
    for (int i = 0; i < n; i++) {
        ans[r[i]] = i + 1;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}