这道题在一定程度上体现了线段树的一种用法，解决的问题是：对于总计n个元素的第i个元素，已知其在[1,i]上部分序列的排名，求第i个元素在所有n个元素中的排名。
当然这道题数据比较水，所以用O(n^2)的直接解法也可以解出，在这里，我也给出自己的O(n^2)解法。
题目大意：
n头乱序的牛排列在一行，每头牛都有一个牌号(1-n)，现在知道所有牛此前有多少头牛的牌号比该牛的牌号要小，求每头牛的牌号。
直接解法(插入式)：
从前向后遍历每一个数据，每次都进行一次插入。
具体来说：例如对于(1,0,1)这样的序列，我们先设brand[1] = 1。
由第一个数据(1)有brand[2] = 2 ————有排名为：(1,2)
由第二个数据(0)有brand[3] = 1，此时遍历此前所有元素，查询到>=brand[3]则加一个排名，得到brand[1] = 2,brand[2] = 3; ——排名(2,3,1)
由第三个数据(1)有brand[4] = 2,此时遍历此前元素，参照上面的方法，得到brand[1] = 3,brand[2] = 4; ——(3,4,1,2)
那么最后能够得到排名(3,4,1,2);
Code如下：
1 //普通的O(n^2)算法-直接的想法 2 //n头牛，已知第i头牛在1-i部分序列的排名，求所有牛的牌号(排名) 3 //Memory: 236K Time:375Ms 4 #include<iostream> 5 #include<cstdio> 6 #include<cstring> 7 using namespace std; 8 #define MAX 8005 9 int n; //cow头量 10 int small[MAX]; //比第i头cow靠前但牌号较小的cow头量 11 int brand[MAX]; //牌号 12 int main() 13 { 14 scanf("%d", &n); 15 brand[1] = 1; 16 for (int i = 2; i <= n; i++) 17 { 18 scanf("%d", &small[i]); 19 brand[i] = small[i] + 1; 20 if (small[i] + 1 != i) //不是排在最后 21 { 22 for (int j = 1; j < i; j++) 23 { 24 if (brand[j] >= brand[i]) //>=该序号则+1 25 brand[j]++; 26 } 27 } 28 } 29 for (int i = 1; i <= n; i++) 30 printf("%d\n", brand[i]); 31 return 0; 32 }
线段树解法：
大体想法就是：用线段树存储一个从1-n的顺序排名，将数据从后向前遍历，每次遍历到某一个位置时，假设原数据为s[]，那么对于s[i]，其在1-i的排名就是s[i]+1，那么在线段树中将[s[i]+1,s[i]+1]区间的sum置为0(减去1)。也就是删去s[i]+1这个排名，这样排名的整体规模就缩小了一个单位，即原为n个元素排名，现在是n-1个元素排名(第s[i]+1排名被删去)，并保留原排名数值不变。
这样不断遍历，不断缩减排名的规模就可以依次反向得到该乱序的牛的牌号，然后顺序输出牌号即可
Code如下：
1 //线段树 2 //n头牛，已知第i头牛在1-i部分序列的排名，求所有牛的牌号(排名) 3 //Memory: 432K Time:47Ms 4 #include<iostream> 5 #include<cstdio> 6 #include<cstring> 7 using namespace std; 8 #define MAX 8005 9 int n; //cow头量 10 int small[MAX]; //比第i头cow靠前但牌号较小的cow头量 11 int brand[MAX]; //牌号 12 //Brand interval数组 13 struct Brands{ 14 int l, r; //牌号区间 15 int sum; //头数 16 }tree[4*MAX]; 17 /*从x开始搭建interval tree*/ 18 void build(int x,int l,int r) 19 { 20 tree[x].l = l; 21 tree[x].r = r; 22 if (l == r){ 23 tree[x].sum = 1; 24 return; 25 } 26 int mid = (l + r) / 2; 27 build(2 * x, l, mid); //left son 28 build(2 * x + 1, mid + 1, r); //right son 29 tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum; 30 } 31 int query(int x, int v) 32 { 33 tree[x].sum--; 34 // Hit! 35 if (tree[x].l == tree[x].r) 36 return tree[x].l; 37 if (v <= tree[2 * x].sum) //<=左结点未删减序列数量 38 query(2 * x, v); 39 else query(2 * x + 1, v - tree[2 * x].sum); 40 } 41 int main() 42 { 43 scanf("%d", &n); 44 for (int i = 2; i <= n; i++) 45 scanf("%d", &small[i]); 46 small[1] = 0; 47 build(1, 1, n); 48 for (int i = n; i >= 1; i--) 49 brand[i] = query(1, small[i] + 1); //牌号 50 for (int i = 1; i <= n; i++) 51 printf("%d\n", brand[i]); 52 return 0; 53 }
ACM/ICPC算法训练 之 数据结构-线段树思想(POJ2182,含O(n^2)插入式解法)
原文：http://www.cnblogs.com/Inkblots/p/4921890.html
