【题解】
参考https://blog.csdn.net/acmer_hades/article/details/46272605。设置数组pre_smaller，其中第i个元素即为输入的第i项，则显然pre_smaller[1] = 0。build_tree建立树结构，分解区间[1, N]，其中每个节的度要么为2，要么为0。query中参数smaller_num表示自身以及队列前方比自己编号小的cows的总数。确实是非常简洁的方法，将线段数组运用得淋漓尽致！不愧是NOI大神
【代码】
#include <iostream>
#include <cstdlib>
using namespace std; #define maxn 100001 int N;
int pre_smaller[maxn], ans[maxn]; struct node
{
int left_val, right_val, len;
}s[*maxn]; void build_tree(int root, int left_val, int right_val)
{
s[root].left_val = left_val;
s[root].right_val = right_val;
s[root].len = right_val - left_val + ;
if (left_val == right_val)return;
build_tree( * root, left_val, (left_val + right_val) / );
build_tree( * root + , + (left_val + right_val) / , right_val);
} int query(int root, int smaller_num)
{
s[root].len--;
if (s[root].left_val == s[root].right_val)return s[root].left_val;
else if (s[ * root].len >= smaller_num)return query( * root, smaller_num);
else return query( * root + , smaller_num - s[ * root].len);
} int main()
{
cin >> N;
for (int i = ; i <= N; i++)cin >> pre_smaller[i];
pre_smaller[] = ;
build_tree(, , N);
for (int i = N; i >= ; i--)ans[i] = query(, pre_smaller[i] + );
for (int i = ; i <= N; i++)printf("%d\n", ans[i]);
return ;
}