这道题在一定程度上体现了线段树的一种用法，解决的问题是：对于总计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如下：
//普通的O(n^2)算法-直接的想法
//n头牛，已知第i头牛在1-i部分序列的排名，求所有牛的牌号(排名)
//Memory: 236K Time:375Ms
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 8005
int n; //cow头量
int small[MAX]; //比第i头cow靠前但牌号较小的cow头量
int brand[MAX]; //牌号
int main()
{
scanf("%d", &n);
brand[] = ;
for (int i = ; i <= n; i++)
{
scanf("%d", &small[i]);
brand[i] = small[i] + ;
if (small[i] + != i) //不是排在最后
{
for (int j = ; j < i; j++)
{
if (brand[j] >= brand[i]) //>=该序号则+1
brand[j]++;
}
}
}
for (int i = ; i <= n; i++)
printf("%d\n", brand[i]);
return ;
}
插入式-解法
线段树解法：
大体想法就是：用线段树存储一个从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如下：
//线段树
//n头牛，已知第i头牛在1-i部分序列的排名，求所有牛的牌号(排名)
//Memory: 432K Time:47Ms
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 8005
int n; //cow头量
int small[MAX]; //比第i头cow靠前但牌号较小的cow头量
int brand[MAX]; //牌号
//Brand interval数组
struct Brands{
int l, r; //牌号区间
int sum; //头数
}tree[*MAX];
/*从x开始搭建interval tree*/
void build(int x,int l,int r)
{
tree[x].l = l;
tree[x].r = r;
if (l == r){
tree[x].sum = ;
return;
}
int mid = (l + r) / ;
build( * x, l, mid); //left son
build( * x + , mid + , r); //right son
tree[x].sum = tree[ * x].sum + tree[ * x + ].sum;
}
int query(int x, int v)
{
tree[x].sum--;
// Hit!
if (tree[x].l == tree[x].r)
return tree[x].l;
if (v <= tree[ * x].sum) //<=左结点未删减序列数量
query( * x, v);
else query( * x + , v - tree[ * x].sum);
}
int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &small[i]);
small[] = ;
build(, , n);
for (int i = n; i >= ; i--)
brand[i] = query(, small[i] + ); //牌号
for (int i = ; i <= n; i++)
printf("%d\n", brand[i]);
return ;
}
线段树-解法