[HDU5592] ZYB's Premutation

题目大意:一个由\([1,n]\)组成的数列，但不知道具体排列，但给出每个前缀的逆序对数目，让你还原排列

Solution

创造一颗\([1,n]\)的权值线段树，初始权值都为\(1\),我们从后往前离线处理，每次拿到一个前缀的逆序对数\(p[i]\)，说明在\(i\)上的这个数字\(a_i\)前面有\(sum=p[i]-p[i-1]\)个数字比它大，所以\(a_i\)是\(a_1,\cdots ,a_i\)中第\(i -sum\)大的数字，查询后这个\(a_i\)对前面就没有用了，需要在权值线段树上删去

Code

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

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

#define pf(x) printf("%d\n",x)

#define lson cur << 1

#define rson (cur << 1) | 1

const int N = 50005;

int num[N << 2], val[N << 2];

int p[N], ans[N];

int n;

void build(int cur, int l, int r){

	num[cur] = r - l + 1;

	if(l == r){

		val[cur] = l;

		return;

	}else{

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

		build(lson, l, mid);

		build(rson, mid + 1, r);

	}

}

int query(int cur, int l, int r, int k){

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

	if(l == r){

//		pf(val[cur]);

		return val[cur];

	}else{

		if(num[lson] >= k){

			return query(lson, l, mid, k);

		}else{

			return query(rson, mid + 1, r, k - num[lson]);

		}

	}

}

void update(int cur, int l, int r, int k){

	num[cur]--;

	if(l == r){

		val[cur] = 0;

		return;

	}else{

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

		if(k <= mid){

			update(lson, l, mid, k);

		}else{

			update(rson, mid + 1, r, k);

		}

	}

}

int main(){

	int t;

	scanf("%d", &t);

	while(t--){

		scanf("%d", &n);

		memset(num, 0, sizeof(num));

		memset(val, 0, sizeof(val));

		build(1, 1, n + 1);//l和r要和数组对应起来，不能建的时候是n+1,query和update时又变成了n

		for(int i = 1, la; i <= n; ++i){

			scanf("%d", &p[i]);

		}

		for(int i = n; i; --i){

			ans[i] = query(1, 1, n + 1, i - p[i] + p[i - 1]);

			update(1, 1, n + 1, ans[i]);

		}

		for(int i = 1; i < n; ++i){

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

		}

		printf("%d\n", ans[n]);

	}

	return 0;

}

Error

\(l\)和\(r\)要和数组对应起来，不能建的时候是\(n+1\),\(query\)和\(update\)时又变成了\(n\)

巴特西

[HDU5592] ZYB's Premutation

[HDU5592] ZYB's Premutation

Solution

Code

Error

最新文章

热门文章