ZYB's Premutation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1029 Accepted Submission(s): 528

Problem Description

Input

In the first line there is the number of testcases T.

For each teatcase:

In the first line there is one number

Output

For each testcase,print the ans.

Sample Input

1 3 0 1 2

Sample Output

3 1 2

这道题的意思就是：你知道有一个1~n的排列，但具体排列你不知道。现在给出1~n每个前缀的逆序数对数，让你还原这个排列。

想法很简单，我们将这个逆序数数列rev从后往前看。我们从最后一个位置往前逐个得出ans。对于第i个前缀和的逆序数对数rev[i],我们得出他的逆序数对数较前一个前缀和的增长量，即up=rev[i]-rev[i-1],那么在i位置前就有up个数是大于当前位置的数字的，所以该位置的数字就是剩下的这些数字里的第i-up大的数字。于是我们把1~n构建一棵权值线段树。初始化每个数字的权值都是1。然后从n~1处理。每一次都query取出第i-up大的数字作为当前位置的答案，然后update将该数字从该权值线段树删除，然后到前一个位置继续相同操作。最后就能得出这样一个正确的排列了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define clr(x) memset(x,0,sizeof(x))
 5 using namespace std;
 6 struct segtree
 7 {
 8     int l,r,val,num;
 9 }tree[400010];
10 int n,m,rev[50010],ans[50010];
11 void init(int i,int l,int r);
12 int query(int i,int k);
13 void update(int i,int pos);
14 int main()
15 {
16     int T;
17     scanf("%d",&T);
18     while(T--)
19     {
20         scanf("%d",&n);
21         clr(rev);
22         clr(ans);
23         for(int i=1;i<=n;i++)
24             scanf("%d",&rev[i]);
25         init(1,1,n);
26         for(int i=n;i>=1;i--)
27         {
28             ans[i]=query(1,i-(rev[i]-rev[i-1]));
29             update(1,ans[i]);
30         }
31         for(int i=1;i<n;i++)
32             printf("%d ",ans[i]);
33         printf("%d
",ans[n]);
34     }
35     return 0;
36 }
37 void init(int i,int l,int r)
38 {
39     tree[i].l=l;
40     tree[i].r=r;
41     tree[i].num=r-l+1;
42     tree[i].val=r;
43     if(l==r)
44         return;
45     int mid=(l+r)>>1;
46     init(i<<1,l,mid);
47     init((i<<1)|1,mid+1,r);
48 }
49 int query(int i,int k)
50 {
51     if(tree[i].l==tree[i].r)
52         return tree[i].val;
53     if(tree[i<<1].num>=k)
54         return query(i<<1,k);
55     else
56         return query((i<<1)|1,k-tree[i<<1].num);
57 }
58 void update(int i,int pos)
59 {
60     tree[i].num--;
61     if(tree[i].l==tree[i].r)
62         return ;
63     if(pos<=tree[i<<1].r)
64         update(i<<1,pos);
65     else
66         update((i<<1)|1,pos);
67     return ;
68 }