SPOJ

题目链接：

题目大意：

根据每个数字的逆序对求出原数组

解题思路：

举个例子：
n = 5
a[ n ] = { 0, 1, 2, 0, 1 };
对于第5个士兵，s[ 5 ] = { 1, 2, 3, 4, 5 };
而与它对应的a[ 4 ] = 1，也就是说在他左边的士兵里，有1个比他小，他在他左边的士兵里排第四，故s[5]里第四小的排名就是他的，对应4
对于第4个士兵，s[ 4 ] = { 1, 2, 3, 5 };没有4表示第四小的排名已经被占
a[ 3 ] = 0, 也就是说他左边的士兵都比他等级高，他的排名就最大，故s[4]里最大的事5，就是他的排名
对于第3个士兵，s[ 3 ] = { 1, 2, 3 };
a[ 2 ] = 2, 表示第 3 个士兵左边的两个士兵等级都比他低，故取s[3]里最小的--1
对于第2个士兵，s[ 2 ] = { 2, 3 };
a[ 1 ] = 1, 表示第 2 个士兵左边的一个士兵等级比他低，故取s[2]里最小的--2
对于第1个士兵，s[ 1 ] = { 3 };
显然第一个士兵排名为3

故解题步骤为：

将1,2,3,...,n添加到集合s里
倒着处理每个士兵：
1.找到s里第a[i]大的数k，赋值给r[i],为i士兵的排名
2.将s里的k剔除

 1 #include<bits/stdc++.h>
 2 #define lowbit(i) (i & (-i))
 3 using namespace std;
 4 const int maxn = 1000005;
 5 int a[maxn];
 6 int tree[maxn], n;
 7 int ans[maxn];
 8 void add(int x, int d)
 9 {
10     while(x <= n)
11         tree[x] += d, x += lowbit(x);
12 }
13 int sum(int x)
14 {
15     int ans = 0;
16     while(x)
17         ans += tree[x], x -= lowbit(x);
18     return ans;
19 }
20 int Find(int x)
21 {
22     int l = 1, r = n;
23     while(l < r)
24     {
25         int mid = (l + r) / 2;
26         if(sum(mid) >= x)
27             r = mid;
28         else l = mid + 1;
29     }
30     return r;
31 }
32 int main()
33 {
34     int T;
35     scanf("%d", &T);
36     while(T--)
37     {
38         memset(tree, 0, sizeof(tree));
39         scanf("%d", &n);
40         for(int i = 1; i <= n; i++)add(i, 1), scanf("%d", &a[i]);
41         for(int i = n; i >= 1; i--)
42             ans[i] = Find(i - a[i]), add(ans[i], -1);
43         printf("%d", ans[1]);
44         for(int i = 2; i <= n; i++)
45             printf(" %d", ans[i]);
46         puts("");
47     }
48     return 0;
49 }