hdu 5592 ZYB's Premutation(线段树查询第k大的数) - dblank

hdu 5592 ZYB's Premutation(线段树查询第k大的数)

ZYB's Premutation

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

Problem Description

ZYB has a premutation P,but he only remeber the reverse log of each prefix of the premutation,now he ask you to
restore the premutation.

Pair (i,j)(i<j) is considered as a reverse log if Ai>Aj is matched.

 

Input

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

For each teatcase:

In the first line there is one number N.

In the next line there are N numbers Ai,describe the number of the reverse logs of each prefix,

The input is correct.

1T5,1N50000

 

Output
For each testcase,print the ans.

 

Sample Input
1 3 0 1 2

 

Sample Output
3 1 2

 

Source

 

Recommend
hujie   |   We have carefully selected several similar problems for you:  5594 5593 5591 5590 5589
先把逆序数前缀和的数组还原成每个数对应的逆序数,然后从最后面开始,就是 i - a[i] 小的数,比赛的时候,我用vector删除元素,终测的时候超时了,用线段树的复杂度是nlogn。vector是n*n,删除的时候效率很低。
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<map>  
#include<vector>  
using namespace std;  
int sum[50050];  
int num[50050];  
int n;  
int s[50050<<2];  
int K;  
void build(int l, int r, int cnt)  
{  
    if (l==r)  
    {  
        s[cnt]=1;  
        return;  
    }  
    int mid=(l+r)>>1;  
    build(l, mid, cnt<<1);  
    build(mid+1 ,r,cnt<<1|1);  
    s[cnt]=s[cnt<<1]+s[cnt<<1|1];  
   // cout<<s[cnt]<<endl;  
}  
void query(int l, int r, int cnt, int k)  
{  
    if(l == r)  
    {  
        K = l;  
        s[cnt] = 0;  
        //cout<<l<<endl;  
        return ;  
    }  
    int mid = (l+r)>>1;  
    if(k<=s[cnt<<1])  
        query(l, mid, cnt<<1, k);  
    else  
        query(mid+1, r, cnt<<1|1, k - s[cnt<<1]);  
    s[cnt] = s[cnt<<1] + s[cnt<<1|1];  
   // cout<<s[cnt]<<endl;  
}  
int main()  
{  
    int t;  
    cin>>t;  
    int ans[50050];  
    while(t--)  
    {  
        scanf("%d", &n);  
        sum[0] = 0;  
        for(int i = 1; i<=n; i++)  
            scanf("%d", &sum[i]);  
        for(int i = 1; i<=n; i++)  
            num[i] = sum[i] - sum[i-1];  
        memset(s, 0, sizeof(s));  
        build(1, n, 1);  
        for(int i = n; i>=1; i--)  
        {  
            query(1, n, 1, i - num[i]);  
            ans[i] = K;  
            //ans[i] = n - K + 1;  
        }  
        query(1, n, 1, n);  
        for(int i = 1; i<=n; i++)  
            if(i == 1)  
                printf("%d", ans[i]);  
           else printf(" %d", ans[i]);  
        printf("\n");  
    }  
    return 0;  
}  

 

相关文章

发表新评论