题解：P8407 [COCI 2021/2022 #6] Superpozicija

Claire0918 · 2025-10-20 21:09:00 · 题解

我们知道一个括号序列合法，当且仅当将 \texttt{(} 当作 1，\texttt{)} 当作 -1 时序列每个位置前缀和非负，且最后和为 0。

如果 z_{a_i} = z_{b_i} = \texttt{(}，那么选哪个对于最后和的影响是相同的，而选较小的一个可以使更多的前缀和增加 1，显然不劣，于是选择较小的一个。z_{a_i} = z_{b_i} = \texttt{)} 的情况是对称的。

如果 z_{a_i} = \texttt{(}, z_{b_i} = \texttt{)}，选择 a_i 时对 [a_i, 2n] 的贡献时 1，对 [b_i, 2n] 的贡献是 0；选择 b_i 时对 [a_i, 2n] 的贡献是 0，对 [b_i, 2n] 的贡献是 -1。我们想优先使最后的和尽量小，于是我们选择 b_i，并且保留一种操作 (a_i, b_i)，可以将 [a_i, 2n] 和 [b_i, 2n] 的贡献加上 1。z_{a_i} = \texttt{)}, z_{b_i} = \texttt{(} 的情况是对称的。

我们现在确定了每个位置的贡献，枚举 i 顺着往后扫。如果当前的前缀和 s_i < 0，那么我们要选择一对 (a_k, b_k) 进行操作。不妨设 a_k \leq b_k，显然有 a_k \leq i，而我们选择哪一对操作对于最后和的影响都是 2，于是我们选择 b_k 最小的一对显然不劣。将 (a_k, b_k) 挂在 a_k 上，维护一个堆表示最小的 b_k 即可，区间加 1 直接打标记 \mathcal{O}(1) 处理，时间复杂度 \mathcal{O}(n\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 1e5 + 10;

int t, n;
char s[maxn << 1];
int a[maxn << 1], tag[maxn << 1], res[maxn];
vector<pair<int, int> > ad[maxn << 1];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q;

int main(){
    scanf("%d", &t);
    while (t--){
        scanf("%d %s", &n, s + 1), res[0] = 0;
        for (int i = 1; i <= n << 1; a[i] = tag[i] = 0, ad[i].clear(), i++);
        for (;!q.empty(); q.pop());
        for (int i = 1; i <= n; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            if (s[x] == '(' && s[y] == '('){
                res[i] = x > y, a[min(x, y)] = 1;
            }else if (s[x] == ')' && s[y] == ')'){
                res[i] = x < y, a[max(x, y)] = -1;
            }else{
                const bool tmp = s[x] == '(';
                x > y && (swap(x, y), 1538), a[s[x] == '(' ? y : x] = -1, res[i] = tmp, ad[x].push_back(make_pair(y, tmp ? i : -i));
            }
        }
        for (int i = 1; i <= n << 1; i++){
            a[i] += a[i - 1] + tag[i];
            for (auto x: ad[i]){
                q.push(x);
            }
            if (a[i] < 0){
                if (q.empty()){
                    res[0] = 1;
                    break;
                }
                a[i]++, (q.top().first > i ? tag[q.top().first] : a[i])++, res[abs(q.top().second)] = q.top().second < 0, q.pop();
            }
        }
        if (res[0] || a[n << 1]){
            printf("-1\n");
        }else{
            for (int i = 1; i <= n; i++){
                printf("%d ", res[i]);
            }
            putchar('\n');
        }
    }

return 0;
}