ZYB's Premutation(有逆序数输出原序列，线段树)

时间：2021-07-03 20:11:45

ZYB's Premutation

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

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.
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
 

题意：

已知【1,i】的逆序数，让你还原这个区间；
思路：用数组记录第i个数前面比a[i]大的数的个数；
用线段树记录当前区间的空缺数；类似与买车票插队那道；然后从最后一个数开始，往线段树中插；a[i]越大代表这个数越小；就往左树插，插到相应位置这个位置被用过了；也就是0；
为什么要从后往前插；因为如果从前往后假设一组数1,2,3,4;插得结果会是4，3，2，1；那样就错了；倒插是1，2，3，4；
代码:
#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define P_ printf(" ")

#define T_T while(T--)

#define mem(x,y) memset(x,y,sizeof(x))

#define ll root<<1

#define rr root<<1|1

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define V(x) tree[x]

const int MAXN=50010;

int tree[MAXN<<2],a[MAXN],ans[MAXN];

int nowans;

void pushup(int root){

	V(root)=V(ll)+V(rr);

}

void made(int root,int l,int r){

	V(root)=r-l+1;

	int mid=(l+r)>>1;

	if(l==r)return;

	made(lson);

	made(rson);

}

void query(int root,int l,int r,int v){

	if(l==r){

		nowans=l;

		V(root)=0;

		return;

	}

	int mid=(l+r)>>1;

	if(v>=V(rr))query(lson,v-V(rr));

	else query(rson,v);

	pushup(root);

}

int main(){

	int T,N;

	SI(T);

	T_T{

		SI(N);

		made(1,1,N);

		int cur,last=0;

		for(int i=0;i<N;i++){

			scanf("%d",&cur);

			a[i]=cur-last;

			last=cur;

		}

		for(int i=N-1;i>=0;i--){

			query(1,1,N,a[i]);

			ans[i]=nowans;

		}

		for(int i=0;i<N;i++){

			if(i)P_;

			printf("%d",ans[i]);

		}puts("");

	}

	return 0;

}



　　




相关文章