设f_ifi是第ii个前缀的逆序对数,p_ipi是第ii个位置上的数,则f_i-f_{i-1}fi−fi−1是ii前面比p_ipi大的数的个数.我们考虑倒着做,当我们处理完ii后面的数,第ii个数就是剩下的数中第f_i-f_{i-1}+1fi−fi−1+1大的数,用线段树和树状数组可以轻松地求出当前第kk个是11的位置,复杂度O(N \log N)O(NlogN).
1 #define cn(i,p,q) for(int i=p;i<=q;i++)
2 #define cn1(i,p,q) for(int i=p;i>=q;i--)
3 #define pr(x) printf("%d\n",x)
4 #define prr(x) printf("%d",x)
5 #define prrr(x) printf(" %d",x)
6 #define sc(x) scanf("%d",&x)
7 #define scc(x) scanf("%lf",&x)
8 #define pr1(x) printf("%.2f\n",x)
9 #include<stdio.h>
10 #include<algorithm>
11 #include<iostream>
12 #include<string.h>
13 #include<stdlib.h>
14 #include<math.h>
15 int que(int l,int r,int k ,int s);
16 void build(int l,int r,int k);
17 void up(int k);
18 const int N=1e6+10;
19 int a[N];
20 int b[N];
21 int c[N];
22 int flag[N];
23 int main(void)
24 {
25
26 int n,j,i,k,p,q;
27 scanf("%d",&n);
28 while(n--)
29 {
30 scanf("%d",&k);
31 for(i=1; i<=k; i++)
32 {
33 scanf("%d",&a[i]);
34 }
35 c[1]=0;
36 for(i=2; i<=k; i++)
37 {
38 c[i]=a[i]-a[i-1];
39 }
40 build(1,k,0);
41 for(i=k; i>=1; i--)
42 {
43 int ff=i-c[i];
44 int ss=que(1,k,0,ff);
45 c[i]=ss;
46 }
47 printf("%d",c[1]);
48 for(i=2; i<=k; i++)
49 {
50 printf(" %d",c[i]);
51 }printf("\n");
52
53 }
54 return 0;
55
56 }
57 void build(int l,int r,int k)
58 {
59 if(l==r)
60 {
61 b[k]=1;
62 flag[l]=k;
63 return ;
64 }
65 build(l,(l+r)/2,2*k+1);
66 build((l+r)/2+1,r,2*k+2);
67 b[k]=b[2*k+1]+b[2*k+2];
68
69 }
70 int que(int l,int r,int k ,int s)
71 {
72 if(b[k]==s&&b[flag[r]]!=0)
73 {
74 b[flag[r]]=0;
75 up(flag[r]);
76 return r;
77 }
78 else if(b[k]<=s)
79 {
80 if(b[2*k+1]<s)
81 {
82 return que((l+r)/2+1,r,2*k+2,s-b[2*k+1]);
83 }
84 else if(b[2*k+1]==s)
85 {
86 return que(l,(l+r)/2,2*k+1,s);
87 }
88 }
89 else if(b[k]>s)
90 {
91 if(b[2*k+1]>=s)
92 {
93 return que(l,(l+r)/2,2*k+1,s);
94 }
95 else return que((l+r)/2+1,r,2*k+2,s-b[2*k+1]);
96 }
97
98 }
99
100 void up(int k)
101 {
102 int kk=(k-1)/2;
103 while(kk>=0)
104 {
105 b[kk]=b[2*kk+1]+b[2*kk+2];
106 if(kk==0)
107 {
108 break;
109 }
110 kk=(kk-1)/2;
111 }
112 }