题解 P9406【[POI2020-2021R3] Nawiasowania】

一个显然的思路是：在排列 \(p\) 的括号串合法的基础上，使得左括号在原括号串中尽量靠左，这样答案更有可能合法。于是我们求出这个原括号尽量靠左的括号串（下文称为“最优括号串”），然后 check 合法性即可。

下文中 \(s\) 是排列 \(p\) 的括号串。

当 \(n=2\) 时，唯一的填法是令 \(s_1\gets\texttt{(},s_2\gets\texttt{)}\)，这个填法显然是最优括号串。

如果我们找出了 \(n=n_0-2\) 的最优括号串，考虑如何找出 \(n=n_0\) 的最优括号串。显然已经填好的左括号是不能动的，因为 \(n=n_0-2\) 时已经是最优括号串，任何移动都会导致括号串不合法。我们先令多出的两位 \(s_{n_0-1}\gets\texttt{)},s_{n_0}\gets\texttt{)}\)，只需要在这个括号串中改一个左括号为右括号，且括号串依然合法即可。

注意到除了 \(s_{n_0}\) 处的右括号，其他的右括号都可以改为左括号。这个性质可以通过 \(n=n_0-2\) 时的最优括号串性质易证。

于是我们用小根堆维护当前所有可以改为左括号的右括号的位置，进行增量构造。小根堆中初始有 \(p_1\)，进行 \(\frac{n}{2}\) 次操作，每次取出小根堆堆顶并对应位置置为左括号，然后将新产生的可改动位置压入堆中即可。

最后 check 答案字符串的合法性并输出。

时间复杂度 \(O(n\log n)\)。

// Problem: P9406 [POI2020-2021R3] Nawiasowania
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9406
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
	uniform_int_distribution<int> dist(L, R);
	return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const int N = 1e6+5;

int n, a[N];
char s[N];
priority_queue<int, vector<int>, greater<int>> heap;

int main() {
	scanf("%d", &n);
	rep(i, 1, n) {
		scanf("%d", &a[i]);
		s[i] = ')';
	}
	s[n+1] = 0;
	heap.push(a[1]);
	rep(i, 1, n/2) {
		s[heap.top()] = '(';
		heap.pop();
		if(i < n / 2) {
			heap.push(a[2*i]);
			heap.push(a[2*i+1]);
		}
	}
	int now = 0;
	rep(i, 1, n) {
		if(s[i] == '(') ++now;
		else --now;
		if(now < 0) return puts("NIE")&0;
	}
	puts(s+1);
	return 0;
}