HDU 5592

原题：

http://acm.hdu.edu.cn/showproblem.php?pid=5592

线段树的变形，先说思路。

题目中给出了当前节点之前的逆序对数，则p[i]-p[i-1]就是对于p[i]来说，新增的逆序数，也就是比p[i]大的数，所以这时要考虑倒着处理，用线段树维护哪些数已经使用，哪些还未使用，p[i]-p[i-1]+1就是在还能用的序列中，第几大的数。我们用1表示数还没用，用0表示已经用了，这里就用到线段树的变形，每个节点维护着当前区间有几个1，我们的原则是先访问线段树的右节点，再左节点，因为右边的数大嘛。

需要注意的是，刚开始要将所有的叶子节点更新为1，再就是，当右节点不满足条件，要进入左节点时，一定用val减去右节点的值。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 50005
 4 int a[maxn],b[maxn],tree[maxn<<2];
 5 int n,k;
 6 void init(){
 7     k = 1;
 8     while(k<n)
 9         k <<= 1;
10     memset(tree,0,sizeof(tree));
11 } 
12 void upgrade(int index,int val){
13     index = index + k - 1;
14     tree[index] += val;
15     index /= 2;
16     while(index){
17         tree[index] = tree[index*2] + tree[index*2+1];
18         index /= 2;
19     }
20 }
21 int query(int index,int l,int r,int val){
22     if(l==r)
23         return l;
24     int m = (l+r)/2;
25     if(tree[index*2+1]>val)
26         query(index*2+1,m+1,r,val);
27     else
28         query(index*2,l,m,val-tree[index*2+1]);
29 }
30 int main(){
31     int t;
32     scanf("%d",&t);
33     while(t--){
34         scanf("%d",&n);
35         init();
36         for(int i = 1;i<=n;i++){
37             scanf("%d",&a[i]);
38             upgrade(i,1);
39         }
40         for(int i = n;i>0;i--){
41             int val = a[i] - a[i-1];
42             b[i] = query(1,1,k,val);
43             upgrade(b[i],-1);
44         }
45         for(int i = 1;i<n;i++)
46             printf("%d ",b[i]);
47         printf("%d
",b[n]);
48     }
49     return 0;
50 }