ZYB's Game
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5592
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:
the first line there is one number N.
1≤T≤100000,1≤N≤10000000
Output
For each testcase,print the ans.
Sample Input
1
3
0 1 2
Sample Output
3 1 2
HINT
题意
题解：
很显然可以发现,a[i]-a[i-1]，就表示在[1,i]中比i大的数有多少个
那么我们倒着做就好了，拿一个树状数组来维护就行了~
代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define maxn 50005
long long a[maxn];
int ans[maxn];
#define lowbit(x) ((x)&(-x)) struct BinaryIndexTree
{
int val[maxn],sz; void init(int sz){
this->sz=sz;
memset(val , , sizeof(int)*(sz+));
} void updata(int pos ,int key){
while(pos<=sz){
val[pos]+=key;
pos+=lowbit(pos);
}
} long long prefixsum(int pos){
long long res=;
while(pos>){
res+=val[pos];
pos-=lowbit(pos);
}
return res;
} int query(int l,int r){
return prefixsum(r)-prefixsum(l-);
} //到第一个大于等于k的位置返回
//若不存在,返回-1
int lower_bound(long long k){
if(prefixsum(sz)<k) return -;
int l = , r = sz;
while(l <= r){
int mid = l + ((r-l)>>);
if(prefixsum(mid) < k) l = mid + ;
else r = mid - ;
}
return l;
} }solver; long long c[maxn];
int main()
{
int t;scanf("%d",&t);
for(int cas=;cas<=t;cas++)
{
memset(a,,sizeof(a));
memset(c,,sizeof(c));
int n;scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%I64d",&a[i]);
for(int i=;i<=n;i++)
c[i]=a[i]-a[i-];
solver.init(n);
for(int i=;i<=n;i++)
solver.updata(i,);
int tmp = ;
for(int i=n;i>=;i--)
{
ans[i]=solver.lower_bound(n-tmp-c[i]);
solver.updata(ans[i],-);
tmp++;
}
for(int i=;i<=n;i++)
{
if(i!=n)
printf("%d ",ans[i]);
else printf("%d\n",ans[i]);
}
}
}