Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 175 Accepted Submission(s): 74
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.
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.
1≤T≤5,1≤N≤50000
Output
For each testcase,print the ans.
Sample Input
1
3
0 1 2
Sample Output
3 1 2
Source
思路：容易想到k = (a[i] - a[i - 1] + 1)就是原序列第i个数的左边比其大的个数，可以从右往左依次计算
用线段树实现：序列中每个存在的位置相当于有一个1，不存在位0，从中找出第k个1所在的位置，找到后删除该数相当于置0
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1|1
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll; const int N = ;
int num[N << ], a[N], ans[N];
void up(int rt) { num[rt] = num[rt << ] + num[rt << |]; }
void build(int l, int r, int rt)
{
if(l == r) {
num[rt] = ;
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
up(rt);
}
void update(int l, int r, int rt, int p)
{
if(l == p && r == p) {
num[rt]--;
return ;
}
int m = (l + r) >> ;
if(p <= m) update(lson, p);
else update(rson, p);
up(rt);
}
int pos;
void get(int l, int r, int rt, int x)
{
if(l == r) {
pos = l;
return;
}
int m = (l + r) >> ;
if(num[rt << ] < x) get(rson, x - num[rt << ]);
else get(lson, x);
}
int main()
{
int _; scanf("%d", &_);
while(_ --)
{
int n; scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
build(, n, );
int c = n;
for(int i = n; i >= ; --i)
{
int d = c - (a[i] - a[i - ]);
get(, n, , d);
update(, n, , pos);
// cout << pos << endl;
ans[i] = pos;
c--;
}
get(, n, , ); ans[] = pos;
for(int i = ; i < n; ++i) printf("%d ", ans[i]);
printf("%d\n", ans[n]);
}
return ;
}