【题解】
参考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大神
【代码】
1 #include <iostream> 2 #include <cstdlib> 3 using namespace std; 4 5 #define maxn 100001 6 7 int N; 8 int pre_smaller[maxn], ans[maxn]; 9 10 struct node 11 { 12 int left_val, right_val, len; 13 }s[4*maxn]; 14 15 void build_tree(int root, int left_val, int right_val) 16 { 17 s[root].left_val = left_val; 18 s[root].right_val = right_val; 19 s[root].len = right_val - left_val + 1; 20 if (left_val == right_val)return; 21 build_tree(2 * root, left_val, (left_val + right_val) / 2); 22 build_tree(2 * root + 1, 1 + (left_val + right_val) / 2, right_val); 23 } 24 25 int query(int root, int smaller_num) 26 { 27 s[root].len--; 28 if (s[root].left_val == s[root].right_val)return s[root].left_val; 29 else if (s[2 * root].len >= smaller_num)return query(2 * root, smaller_num); 30 else return query(2 * root + 1, smaller_num - s[2 * root].len); 31 } 32 33 int main() 34 { 35 cin >> N; 36 for (int i = 2; i <= N; i++)cin >> pre_smaller[i]; 37 pre_smaller[1] = 0; 38 build_tree(1, 1, N); 39 for (int i = N; i >= 1; i--)ans[i] = query(1, pre_smaller[i] + 1); 40 for (int i = 1; i <= N; i++)printf("%d ", ans[i]); 41 return 0; 42 }