题目
题目描述
Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow。
输入描述
- Line 1: A single integer, N
- Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.
输出描述
- Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.
示例1
输入
5
1
2
1
0
输出
2
4
5
3
1
题解
知识点：树状数组，倍增，枚举。
首先用树状数组维护右侧出现的数字，随后需要二分一个 \(x\ 通过比较 \(x - cnt_{<x} -1 < a_i\ 得知 \(x\ 是否小了还是大了，从而找到第一个 \(x - cnt_{<x} -1 = a_i\ 的点。注意，条件不能为 \(x - cnt_{<x} -1 \leq a_i\，因为可能会出现连续一段刚好等于 \(a_i\ 的点，而我们只需要第一个的下标即可，如果用这个条件，我们得到的是最后一个下标。
另外，二分套树状数组查询的复杂度是对数平方的，并不是最优的。我们可以直接使用树状数组本身的倍增性质进行二分，是最优的对数复杂度。我封装了两个常用的函数，大于等于 lower_bound 和大于 upper_bound 。
lower_bound 查询即可。
空间复杂度 \(O(n\
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0 { init(_n; }
void init(int _n {
n = _n;
node.assign(n + 1, T(;
}
void update(int x, T val { for (int i = x;i <= n;i += i & -i node[i] += val; }
T query(int x {
T ans = T(;
for (int i = x;i >= 1;i -= i & -i ans += node[i];
return ans;
}
T query(int l, int r { return query(r - query(l - 1; }
int lower_bound(T val {
int pos = 0;
for (int i = 1 << __lg(n; i; i >>= 1 {
if (pos + i <= n && node[pos + i] < val {
pos += i;
val -= node[pos];
}
}
return pos + 1;
}
int upper_bound(T val {
int pos = 0;
for (int i = 1 << __lg(n; i; i >>= 1 {
if (pos + i <= n && node[pos + i] <= val {
pos += i;
val -= node[pos];
}
}
return pos + 1;
}
};
int a[8007];
int main( {
std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
int n;
cin >> n;
for (int i = 2;i <= n;i++ cin >> a[i];
Fenwick<int> fw(n;
for (int i = 1;i <= n;i++ fw.update(i, 1;
vector<int> ans(n + 1;
for (int i = n;i >= 1;i-- {
ans[i] = fw.lower_bound(a[i] + 1;
fw.update(ans[i], -1;
}
for (int i = 1;i <= n;i++ cout << ans[i] << '\n';
return 0;
}