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

# 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

#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;
}