hdu 5592 ZYB's Premutation(线段树优化)

设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 }

巴特西

hdu 5592 ZYB's Premutation(线段树优化)

最新文章

热门文章