题解 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;
}