poj 2182 Lost Cows （線段樹）

 Lost Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8838 Accepted: 5657

Description

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

Input

* Line 1: A single integer, N

* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

Source

USACO 2003 U S Open Orange
這道題算是我的線段樹處女題吧，感覺線段樹的應用真心的廣啊，對線段樹還沒達到那種靈活運用的地步，線段樹的應用范圍比樹狀數組還要廣一些，這道題也可以用樹狀數組來做，樹狀數組和線段樹要掌握好啊，比較重要，要達到能夠靈活運用！！ 對這種英語題還是比較無感啊，開始對題意都理解不了，英語能力還有待加強，剛開始看這道題的樣例輸入，看5個輸入，但是只有4個輸入，開始都沒看懂，其實這裡是一個隱含條件，亂序排的第一個，前面沒有元素了，所以前面比它小的就沒有，所以第一個就是0，所以樣例就應該是5（0,1,2,1,0），看了好久，才總算好久把題意看懂，然後還沒找到和線段樹的切入點； 題意就是：給你亂序排成一列的牛，給你每頭牛前面有多少頭牛比它的編號小，求排隊後從前往後數，每頭牛的編號； 參考了大神的思路，首先建立一顆線段樹，然後從後往前掃描，遇到序號i，說明是剩余序號的i+1號，然後就借助線段樹查找，看一個區間內的數字能否滿足要找的那個數成為i+1，能就遞歸左子樹，不能就遞歸右子樹，直到葉子節點，葉子節點的值就是原來的編號 下面是ac的代碼；

#include 
#define N 8002
int num[N],ans[N];
struct segment
{
    int l,r,len;
}s[N];
void build(int root,int l,int r)//建立樹
{
   s[root].l=l;
   s[root].r=r;
   s[root].len=r-l+1;//線段的區間（按照題意）
   if(l==r)return;
   build(2*root,l,(l+r)/2);
   build(2*root+1,(l+r)/2+1,r);
}
int query(int root,int k)//查找線段樹
{
    s[root].len--;//每查找一次，區間就減1，說明找到了一個編號，就刪除那個節點；
    if(s[root].l==s[root].r) return s[root].l;//說明找到葉子節點
    else if(k<=s[2*root].len)
    {return query(2*root,k);}//遞歸左子樹
    else
    {return query(2*root+1,k-s[2*root].len);}//遞歸右子樹
}
int main()
{
   int n;
   scanf("%d",&n);
   for(int i=2;i<=n;i++)
     scanf("%d",&num[i]);
    num[1]=0;//第一個編號為0；
    build(1,1,n);
    for(int i=n;i>=1;i--)//倒序
        ans[i]=query(1,num[i]+1);
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

這道題還可以用數組數組做，換一種思路，明天再做，（未完待續。。）