匹配
题目描述
一个长度为 \(2n\) 的序列 \(a\)，其中 \(1\dots n\) 中所有数都恰好出现两次。
相同数字填相同括号，使其变成合法字符串，同时要字符串字典
序最小。
数据范围
\(1 ≤ n ≤ 10^6\)。
分析
我们括号匹配的经典做法就是把左括号看作 \(+1\)，右括号看作 \(-1\)，那么任意一个位置上的前缀和必须 \(\geq0\)，且最后一个位置的前缀和必须为 \(0\)。
这个可以引申出来一个定理：
对于第 \(i\) 个左括号一定满足其位置 \(pos\leq 2i-1\)。
显然的，因为如果不满足就说明前面的右括号多了，也就是上一个前缀和出现了负数。
那么我们就转化为了处理左括号与这个的偏序关系，又因为字典序天然的贪心，所以说我们从前往后枚举能不能填左括号，如果能填就尽量填。
那怎么判断呢？我们只需要判断这个位置能不能找到偏序关系即可，而且与它数字相同的那一组也要满足。
这个思路很巧妙，位置用 set 维护就行了。
代码
时间复杂度 \(\mathcal{O}(n\log n)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <set>
#define int long long
#define N 1000006
using namespace std;
int p[N << 1],n,ans[N << 1],nxt[N],pre[N];
set<int> st;
signed main(){cin >> n;for (int i = 1;i <= 2 * n;i ++) scanf("%lld",&p[i]);if (n & 1) return puts(":("),0;for (int i = 1;i <= 2 * n;i ++)if (!pre[p[i]]) pre[p[i]] = i;else nxt[p[i]] = i;for (int i = 1;i <= n;i ++) st.insert(2 * i - 1);for (int i = 1;i <= 2 * n;i ++)if (i == pre[p[i]]) {auto t1 = st.lower_bound(pre[p[i]]),t2 = st.lower_bound(nxt[p[i]]);if (t1 != st.end() && t2 == t1) t2 = st.upper_bound(*t1);if (t2 != st.end()) st.erase(t1),st.erase(t2);else ans[i] = ans[nxt[p[i]]] = 1; }if (st.size()) return puts(":("),0;for (int i = 1;i <= 2 * n;i ++) putchar(ans[i] ? ')' : '(');return 0;
}