poj2182

题目意思：一个1-n的排列，给出每个数前面比他小的数的个数，求该序列

思路：很明显从低往前确定数，比如序列为 1 2 1 0

那么最后一个一定是 1,因为前面没比他小的，

倒数第二个为3,因为除去1,他是第二大的。。。。以此类推

那么就变成模拟了。。所以我们可以用平衡树，或者线段树做，但是代码有点长。。

所以自然想到用树状数组了。。

具体如下：刚开始给每个位置赋值为1,找到这个数，那么就删掉。当前第k大实际上就是前面和为k的那个数。。。。输出并删除

这样就要用到二分找第k大的。。

但一个问题是删完后会出现不只一个和为k的数，，解决办法只要取第一个就行了（想想就知道了）

 1 /*
 2   Source:poj2182
 3   Time:2013.5.1
 4   State:Accepted
 5 */
 6 #include <iostream>
 7 #include <cstring>
 8 #include <cstdio>
 9 #include <cmath>
10 #include <algorithm>
11 #define MXN 10000
12 using namespace std;
13 int n, a[MXN], sum[MXN], ans[MXN];
14 bool  bo[MXN];
15 
16 int lowbit(int t){ return t & (-t); } //计算t末尾的0的个数，也可以用 t&(t ^ (t -1)) 的表达式求
17 
18 void updata(int k, int data){  //插入点（往其父节点更新）
19     for (int i = k; i <= n; i += lowbit(i))
20       sum[i] += data;
21 }
22 
23 int getsum(int k){ //求和（往前，其并列节点）
24     int ret = 0;
25     for (int i = k; i > 0; i -= lowbit(i))
26         ret += sum[i];
27     return ret;
28 }
29 
30 void init(){
31     scanf("%d", &n);
32     for (int i = 1; i <= n; ++i)
33        updata(i, 1);
34     for (int i = 1; i < n; ++i)
35        scanf("%d", &a[i]);
36 }
37 
38 int search(int x){
39     int l = 1, r = n, mid, nowsum;
40     while (l < r){
41        mid = l + r >> 1,
42        nowsum = getsum(mid);
43        if (nowsum < x) l = mid + 1;
44        else r = mid;
45     }
46     return l;
47 }
48 
49 void solve(){
50     int k;
51     a[0] = 0;
52     for (int i = n - 1; i >= 0; --i){
53        k = search(a[i] + 1);
54        ans[i] = k;
55        updata(k, -1);
56     }
57     for (int i = 0; i < n; ++i)
58         printf("%d\n", ans[i]);
59 
60 }
61 
62 int main(){
63     freopen("poj2182.in","r", stdin);
64     freopen("poj2812.out","w", stdout);
65     init();
66     solve();
67 }