程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5338 ZZX AND PERMUTATIONS 線段樹

HDU 5338 ZZX AND PERMUTATIONS 線段樹

編輯:關於C++

鏈接

多校題解

胡搞。。。

題意太難懂了。。

 

ZZX and Permutations

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



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
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) pt(x / 10);
	putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair pii;
const double eps = 1e-9;
const int N = 200000 + 10;
#define L(x) tree[x].l
#define R(x) tree[x].r
#define M(x) tree[x].ma
#define ls (id<<1)
#define rs (id<<1|1)
struct node {
	int l, r;
	int ma;
}tree[N << 2];
int a[N], p[N];
void Up(int id) {
	M(id) = max(M(ls), M(rs));
}
void build(int l, int r, int id) {
	L(id) = l; R(id) = r;
	if (l == r) { M(id) = a[l];return; }
	int mid = (l + r) >> 1;
	build(l, mid, ls); build(mid + 1, r, rs);
	Up(id);
}
void update(int pos, int id) {
	if (L(id) == R(id))
	{
		M(id) = -1;return;
	}
	int mid = (L(id) + R(id)) >> 1;
	if (pos <= mid)update(pos, ls);
	else update(pos, rs);
	Up(id);
}
int query(int l, int r, int id) {
	if (l == L(id) && R(id) == r)return M(id);
	int mid = (L(id) + R(id)) >> 1;
	if (r <= mid)return query(l, r, ls);
	else if (mid < l)return query(l, r, rs);
	else return max(query(l, mid, ls), query(mid + 1, r, rs));
}
int n;
int use[N], num[N];
pii b[N];
int ans[N];
void getcir(int l, int r) {
	if (l > r)return;
	for (int i = l; i <= r; i++) {
		if (use[a[i]])continue;
		int to = i + 1;
		if (to > r) to = l;
		ans[a[i]] = a[to];
		use[a[i]] = 1;
		num[a[to]] = 1;
		update(i, 1);
	}
}
int getmax(int l, int r) {
	if (l > r)return -1;
	return query(l, r, 1);
}
int hehe[N];
sets;
int main() {
	int T;rd(T);
	while (T--) {
		s.clear();
		s.insert(0);
		rd(n);
		for (int i = 1; i <= n; i++) {
			rd(a[i]);
			p[a[i]] = i;
			use[i] = num[i] = false;
			b[i] = { a[i], i };
			ans[i] = 0;
		}
		build(1, n, 1);
		sort(b + 1, b + 1 + n);
		int top = 0;
		for (int i = 1; i <= n; i++) {
			if (use[i])continue;
			int idx = b[i].second;
			int t[3] = { -1, -1, -1 };
			if (idx < n && !num[a[idx+1]])t[0] = a[idx + 1];
			top = -(*s.upper_bound(-idx));
			t[1] = getmax(top + 1, idx - 1);
			if (num[i]==false)t[2] = i;
			if (t[0] > max(t[1], t[2]))
			{
				ans[i] = t[0]; use[i] = 1;
				num[t[0]] = 1; 
				update(idx + 1, 1);
			}
			else if (t[1] > max(t[0], t[2]))
			{
				getcir(p[t[1]], idx);
				s.insert(-idx);
			}
			else {
				getcir(idx, idx);
				s.insert(-idx);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			pt(ans[i]);i == n ? putchar('
') : putchar(' ');
		}
	}
	return 0;
}
/*
99
3
1 3 2
ans: 3 2 1
5
1 5 2 3 4
ans: 5 3 4 2 1
 
5
5 2 3 4 1
ans : 5 3 4 1 2
 
7
6 7 1 3 2 5 4
ans:7 5 3 4 2 6 1
 
1
8
1 3 6 4 8 7 2 5
 
1
5
3 2 4 5 1
 
*/


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved