pku 2182_线段树简单应用

题解：题目大意是说农场里有很多奶牛，每一头奶牛有唯一的标记号。在事先并不知道所有奶牛情况下，记录员从第一头牛开始记录数据。从第二头牛开始，每次都要计算有几头牛的标记号比当前这头牛的标记号要小，即有几头牛排在这头牛的前面。

线段树的经典应用，当然不是唯一方法。举个例子说明一下题意~

比如：n = 3

序列1 2 3中每个元素前面大于它的元素个数分别为0 1 2

输入为：0 1 1

则从最后一个1开始向前看，1 2 3 中前面大于该元素的元素个数为1的为数字1，因此选择数字1，然后将1从序列中删除（1 2 3->2 3，0 1 2->0 1）。然后看倒数第二个1。依此类推。

源码：

Problem: 2182		User: moxiaomomo
Memory: 420K		Time: 16MS
Language: C++		Result: Accepted

#include<iostream>
using namespace std;
struct Node
{
    int l;
    int r;
    int cnt;//在[l,r]区间中的个数
};
Node T[16*1024];
int a[8005];
int ans[8005];
int n;
//建立线段树
void build(int l,int r,int u)
{
    T[u].l=l;
    T[u].r=r;
    T[u].cnt=r-l+1;
    if(l<r)
    {
        build(l,(l+r)/2,2*u);
        build((l+r)/2+1,r,2*u+1);
    }
}
//每次找到一个点后，删除该点，并修改路径值
void del(int c,int root) 
{
    if(T[root].l == T[root].r)
    {
        ans[n]=T[root].l;   //找到所求的点
        T[root].cnt=0;  
        return ;
    }
    if(c<=T[2*root].cnt)
        del(c,2*root);
    else
        del(c-T[2*root].cnt,2*root+1);
    T[root].cnt--;       //删除一个点后，父节点中的数值和减1
}
int main()
{
    int N;
    scanf("%d",&N);
    int i;
    a[1]=0;
    for(i=2;i<=N;++i)
        scanf("%d",&a[i]);
    build(1,N,1);
    for(n=N;n>0;--n)
    {
        del(a[n]+1,1);
    }
    for(i=1;i<=N;++i)
        printf("%d/n",ans[i]);
    return 0;
}