<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
树状数组+二分查找
这个问题和楼兰图腾正好反过来,每头牛的高度可以抽象为一个整数集合,一头牛前面有$k$头比它矮,就相当于集合中有$k$个数比当前数小,这相当于维护一个有序集合,依次求出当前第$k+1$小数并把它删除。虽然可以用AVL等平衡查找树,但应该不会有谁觉得这些玩意容易实现的叭(考研都不要求手撕AVL等平衡查找树,至于STL的map或者set容器,迭代器只能++或者–,不能随机存取,可能会被针对,就不展示了)
下面来解释比较巧妙的树状数组法
假设$arr$全1(假想一下即可,类中并未包含$arr$),用来表示元素的存在位,则可以用$base$前缀和为$k$时的前缀长度表示位序为$k$的元素,原理可用下图表示:
假设集合中含1、2、3、4,那么第3位的元素是3,即$preSum(3)=3$,删除3之后,$arr[3]$变为0(减去1),那么就变成了$preSum(4)=3$,第3位的元素变成了4。全1的$arr$对应到$base$中,相当于$base[i]=lowbit(i)$,可对照树状数组类中$base$的特性验证
查找位序为$k$的元素时可利用$preSum$的单调不减性,借助1~n范围内的二分查找实现,详情请见注释
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class BinaryIndexedTree {
private:
//length同时表示长度和范围
vector<int> base, seq;
int length = 0;
int lowbit(int x) {
return x & -x;
}
//相当于把集合1~n中值为id的元素去掉
void remove(int id) {
for (int i = id; i <= length; i += lowbit(i)) {
base[i]--;
}
}
//相当于查找位序为id的元素
int preSum(int id) {
int sum = 0;
for (int i = id; i > 0; i -= lowbit(i)) {
sum += base[i];
}
return sum;
}
public:
BinaryIndexedTree(int n) {
length = n;
base.resize(n + 1);
seq.resize(n + 1);
base[1] = 1;//lowbit(1)还是1
for (int i = 2; i <= n; i++) {
cin >> seq[i];
//集合1~n和base的前缀和一一对应了,这么做相当于有了个全1的arr
base[i] = lowbit(i);
}
}
//找到当前存在的第k小元素,删除它并返回它的值
//参数id表示牛出现的位序,用来取得它对应的k
int smallestKthNum(int id) {
//二分查找的范围固定是1~n
int k = seq[id] + 1, low = 1, high = length;
while (low < high) {
int mid = (low + high) / 2;
//前缀和可以证明是单调不减的,可以利用二分查找
if (preSum(mid) >= k) high = mid;
else low = mid + 1;
}
//找到了再去掉
remove(high);
return high;
}
};
vector<int> ans;
template<class T>
ostream& operator<<(ostream& cout, vector<T> v) {
if (!v.empty()) {
for (int i = 0; i < v.size() - 1; i++) cout << v[i] << endl;
cout << v.back();
}
return cout;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
BinaryIndexedTree BIT(n);//基于树状数组,构建集合1~n
for (int i = n; i > 0; i--) ans.push_back(BIT.smallestKthNum(i));
reverse(ans.begin(), ans.end());
cout << ans << endl;
return 0;
}