POJ2182 Lost Cows 树状数组

一群牛，编号为1到n，但是编号乱了，已知每只牛的前面有多少只编号比其小，求出牛的编号。

插点问段。

这道题要从后面反推回来，比如最后的一只牛，知道有a只编号比它小，则它的编号为a+1。

update 更新已经确定的编号，

sum(i) 查询已经确定的编号中（后面的牛的编号都确定了），有多少个比i小。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 const int MAXN=8000+5;
 5 int c[MAXN];
 6 int a[MAXN];
 7 int ans[MAXN];
 8 int tot;
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 void update(int x,int num,int n)
14 {
15     while(x<=n){
16         c[x]+=num;
17         x+=lowbit(x);
18     }
19 }
20 int sum(int x)
21 {
22     int temp=0;
23     while(x>0){
24         temp+=c[x];
25         x-=lowbit(x);
26     }
27     return temp;
28 }
29 int main()
30 {
31     int n;
32     while(scanf("%d",&n)!=EOF){
33         memset(c,0,sizeof(c));
34         memset(ans,0,sizeof(ans));
35         tot=n;
36         a[0]=a[1]=0;
37         for(int i=2;i<=n;i++)
38             scanf("%d",&a[i]);
39         for(int i=n;i>0;i--){
40             for(int j=a[i]+1;j<=n;j++){
41                 if(1+sum(j)+a[i]==j){
42                     ans[tot]=j;
43                     break;
44                 }
45             }
46             update(ans[tot],1,n);
47             tot--;
48         }
49         for(int i=1;i<=n;i++){
50             printf("%d
",ans[i]);
51         }
52     }
53     return 0;
54 }

poj2182