程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDOJ 5338 ZZX and Permutations 線段樹+樹狀數組

HDOJ 5338 ZZX and Permutations 線段樹+樹狀數組

編輯：關於C++

[題意]:

給一個排列加上表示循環的括號,問如何讓1到n的對應的字典序最大.

從1開始貪心每個數字可以往三個地方走,右邊第一個,跳轉到左邊的某一個,和自己構成循環

對於走到右邊第一個的情況,只要判斷右邊的那個有沒有被占據就可以了,如果可以和右邊的互換,那麼需要在線段樹中將右邊的數置為0

跳轉到左邊的某一個,一個數如果跳轉到左邊的某一個則說明左邊的那個是括號開頭這個數是括號結尾,用一個線段樹查詢區間裡的最大值,由於括號間是不能重疊的,所以需要用樹狀數組二分一下左邊界.如果這個數是要跳轉到左邊的某個數,則要對右括號的位置在樹狀數組裡+1,表示這裡已經有一個完整的括號了

對於2 1 3 這種情況(2)(1 3)的話得到的字典序最大,所以一個數有時候也是可以跳轉到自己的

ZZX and Permutations

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 775 Accepted Submission(s): 244

Problem Description ZZX likes permutations.

ZZX knows that a permutation can be decomposed into disjoint cycles(see https://en.wikipedia.org/wiki/Permutation#Cycle_notation). For example:
145632=(1)(35)(462)=(462)(1)(35)=(35)(1)(462)=(246)(1)(53)=(624)(1)(53)……
Note that there are many ways to rewrite it, but they are all equivalent.
A cycle with only one element is also written in the decomposition, like (1) in the example above.

Now, we remove all the parentheses in the decomposition. So the decomposition of 145632 can be 135462,462135,351462,246153,624153……

Now you are given the decomposition of a permutation after removing all the parentheses (itself is also a permutation). You should recover the original permutation. There are many ways to recover, so you should find the one with largest lexicographic order.
Input First line contains an integer t, the number of test cases.
Then t testcases follow. In each testcase:
First line contains an integer n, the size of the permutation.
Second line contains n space-separated integers, the decomposition after removing parentheses.

n≤105. There are 10 testcases satisfying n≤105, 200 testcases satisfying n≤1000.
Output Output n space-separated numbers in a line for each testcase.
Don't output space after the last number of a line.
Sample Input

2
6
1 4 5 6 3 2
2
1 2

Sample Output

4 6 2 5 1 3
2 1

Author XJZX
Source 2015 Multi-University Training Contest 4

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月03日 星期一 15時51分35秒
File Name     :HDOJ5338.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

const int maxn=100100;

int n;
int nb[maxn],wz[maxn];
int sed[maxn<<2];
int mx[maxn<<2];

#define lrt rt<<1
#define rrt rt<<1|1
#define lson l,m,lrt
#define rson m+1,r,rrt

void push_up(int rt)
{
	mx[rt]=max(mx[lrt],mx[rrt]);
}

void push_down(int rt)
{
	if(sed[rt])
	{
		mx[rrt]=mx[lrt]=0;
		sed[rrt]=sed[lrt]=0;
		sed[rt]=0;
	}
}

void build(int l,int r,int rt)
{
	sed[rt]=mx[rt]=0;
	if(l==r)
	{
		mx[rt]=nb[l];
		return ;
	}
	int m=(l+r)/2;
	build(lson); build(rson);
	push_up(rt);
}

int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R) return mx[rt];

	push_down(rt);
	int m=(l+r)/2;
	int ret=0;
	if(L<=m) ret=max(ret,query(L,R,lson));
	if(R>m) ret=max(ret,query(L,R,rson));
	return ret;
}

void update(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		sed[rt]=1;
		mx[rt]=0;
		return ;
	}

	push_down(rt);
	int m=(l+r)/2;
	if(L<=m) update(L,R,lson);
	if(R>m) update(L,R,rson);
	push_up(rt);
}

void show(int l,int r,int rt)
{
	printf(%d: %d <----> %d mx: %d
,rt,l,r,mx[rt]);
	if(l==r) return;
	int m=(l+r)/2;
	show(lson); show(rson);
}

int ans[maxn];
bool used[maxn];

int tree[maxn];

inline int lowbit(int x) { return x&(-x); }

void add(int p,int v=1)
{
	for(int i=p;iself||right>self)
			{
				if(right>left)
				{
					ans[i]=right;
					used[wz[right]]=true;
					update(wz[right],wz[right],1,n,1);
				}
				else
				{
					ans[i]=left;

					/// link circle
					for(int j=wz[left];j