谜一样的牛

树状数组 在线处理序列中比k大的数量 二分查找 T4 244. 谜一样的牛 - AcWing题库 有 $n$ 头奶牛，已知它们的身高为 $1\sim n$ 且各不相同，但不知道每头奶牛的具体身高。

现在这 $n$ 头奶牛站成一列，已知第 $i$ 头牛前面有 $A_i$ 头牛比它低，求每头奶牛的身高。

输入格式

第 $1$ 行：输入整数 $n$。

第 $\mathrm{2..}n$ 行：每行输入一个整数 $A_i$，第 $i$ 行表示第 $i$ 头牛前面有 $A_i$ 头牛比它低。
（注意：因为第 $1$ 头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含 $n$ 行，每行输出一个整数表示牛的身高。

第 $i$ 行输出第 $i$ 头牛的身高。

数据范围

$1\le n\le 10^5$

输入样例：

5
1
2
1
0

输出样例：

2
4
5
3
1

思路

可以先手动逆序来求解： 对于样例 0 1 2 1 0, 最后一个数前面有0个比它小的, 而1到5每个数又只出现一次, 因此该数就是1。 而对于倒数第二个数前面有1个比它小的, 且此时已经确定了1的位置, 还剩下 2 3 4 5 四个数, 故这个位置上的数就是第二个数 3。 至此可以归纳出一个方法：逆序依次求解, 当前位置的数 $i$ 就是剩余第 $h[i]+1$ 个能选数, $h[i]$ 为 $i$ 之前有几个数比 $i$ 数小。

朴素可以用 $O(n^2)$ 的方式枚举求解, 这里的复杂度肯定过不了。

spray平衡树可以很好的解决这类问题, 但代码太过复杂。这里可以用树状数组解决。 只需要实现两个操作：

• 得到剩余第k个数
• 删除一个数

把树状数组叶子节点都初始化为1, 删除时就将1删去。这样前缀和的含义就是剩余点的数量。

还是看样例, 继续刚才枚举的地方, 开始选倒数第三个数： $i$ 从1到5求 $sum(i)$ 的值为 $sum(i):0,1,1,2,3$ 此时还剩下 2 4 5 三个数可以选, 而倒数第三个数前面有两个比它小的, 显然只能选最后一个 5。 多推几个可以发现, 对应的第一个 $sum(i)>=h[i]+1$ 的就是该放在位置上的数。 而 $sum(i)$ 组成的序列又是单调递增的, 故可以使用二分来以 $O(\log n)$ 的复杂度查询。

总复杂度为 树状数组嵌套二分 $O(\log n^2)$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int t[N*2];
int a[N], ans[N];
int n;
 
int lowbit(int x)
{
    return x & -x;
}
 
void add(int i, int c)
{
    for(i; i <= n; i+=lowbit(i)) t[i] += c;
}
 
int sum(int u)
{
    int res = 0;
    for(int i = u; i; i -= lowbit(i)) res += t[i];
    return res;
}
 
int main()
{
    cin >> n;
    for(int i = 2; i <= n;i ++) cin >> a[i];
    
    for(int i = 1; i <= n;i ++) t[i] = lowbit(i);
    
    for(int i = n; i >= 1; i--)
    {
        int k = a[i] + 1;
        int l = -1, r = n+1;
        while(l != r - 1)
        {
            int mid = l + r >> 1;
            if(sum(mid) < k) l = mid;
            else r = mid;
        }
        ans[i] = r;
        add(r, -1);
    }
    
    for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
    
    return 0;
}