设f_if​i​​是第ii个前缀的逆序对数,p_ip​i​​是第ii个位置上的数,则f_i-f_{i-1}f​i​​−f​i−1​​是ii前面比p_ip​i​​大的数的个数.我们考虑倒着做,当我们处理完ii后面的数,第ii个数就是剩下的数中第f_i-f_{i-1}+1f​i​​−f​i−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
     
       10 #include
      
        11 #include
       
         12 #include
        
          13 #include
         
           14 #include
          
            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) 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 }