2025牛客暑期多校训练营6——Problem L. 最小括号串（括号匹配，） · znzryb
## 思路讲解
离AC之差一步之遥。
那为什么要倒着遍历那？说实话，我也不知道。
这个是
证明：上述过程相当于，一开始将所有的左括号放在前 n 个位置，即字
典序最小的合法括号串。当枚举到的区间带来硬性需求时，我们将最靠
右的左括号移动到当前区间的左端点。这样的操作显然是最优的。时间
复杂度 O(n + m log m)。
## AC代码
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78588028](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78588028)
::: 源代码
```cpp
// by Gospel_rock
// from template_cpp
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using vdb = vector<DB>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
// char S[MAXN];
inline void __(){
cin>>N>>M;
vpll lr;
vector<char> S(2*N+5);
vll A(2*N+5);
bool isN=false;
FOR(i,0,M-1){
ll l,r;
cin>>l>>r;
if(l!=1){
lr.EB(l,r);
}
if(l==2*N){
isN=true;
}
}
if(isN){
cout<<-1<<"\n";
return;
}
sort(all(lr),greater<>());
vpll llr;
if(!lr.empty()){
ll l=lr[0].FI,r=lr[0].SE;
FOR(i,1,SZ(lr)-1){
ll ll=max(l,lr[i].FI),rr=min(r,lr[i].SE);
if(ll>rr){
llr.EB(l,r);
l=lr[i].FI;r=lr[i].SE;
}else{
l=ll;
r=rr;
}
}
llr.EB(l,r);
}
S[1]='(';A[1]=1;
FOR(i,0,SZ(llr)-1){
S[llr[i].FI]='(';
A[llr[i].FI]=1;
}
vll Sum(2*N+5);
FOR(i,1,2*N){
if(A[i]==0){
A[i]=-1;
}
Sum[i]=Sum[i-1]+A[i];
}
ll N2=2*N;
#ifdef LOCAL
FOR(i,1,N2){
cerr<<Sum[i]<<" ";
}
cerr<<"\n";
// FOR(i,1,N2){
// cerr<<S[i]<<" ";
// }
// cerr<<"\n";
FOR(i,0,SZ(llr)-1){
debug(llr[i].FI);
debug(llr[i].SE);
}
#endif
if(Sum[2*N]>0){
cout<<-1<<"\n";
return;
}
ll sum=Sum[N2];
FOR(i,1,N2){
if(S[i]!='('){
if(sum<0){
sum+=2; // -1变成+1，+2。
S[i]='(';
}else{
S[i]=')';
}
}
}
// ())((((((())))))
sum=0;
FOR(i,1,N2){
if(S[i]=='('){
sum+=1;
}else{
sum-=1;
}
// 匹配失败（对于这个右括号，前面已经没有左括号匹配了）
if(sum<0){
cout<<-1<<"\n";
return;
}
}
FOR(i,1,N2){
cout<<S[i];
}
cout<<"\n";
}
/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78588028
1
2 3
1 2
2 3
3 4
()()
*/
```
:::
还有一种树状数组解法。
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)4e5+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
ll tr[MAXN];
ll lowbit(ll x){
return x&(-x);
}
void add(ll p,ll x){
for(int i=p;i<=2*N;i+=lowbit(i)){
tr[i]+=x;
}
}
ll query(ll p){
ll res=0;
for(int i=p;i>0;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
ll query(ll l,ll r){
l-=1;
ll res=query(r)-query(l);
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N>>M;
FOR(i,0,2*N+5){
tr[i]=0;
}
vll A(2*N+5);
vpll lr;
FOR(i,1,M){
ll l,r;
cin>>l>>r;
lr.EB(l,r);
}
sort(all(lr),greater<>());
FOR(i,0,M-1){
auto &[l,r]=lr[i];
if(query(l,r)>0) continue;
add(l,1);
A[l]=1;
}
A[1]=1;
ll N2=2*N;
vll Sum(N2+5);
FOR(i,1,N2){
if(A[i]!=1) A[i]=-1;
Sum[i]=Sum[i-1]+A[i];
}
if(Sum[N2]>0){
cout<<-1<<"\n";
return;
}
ll sum=Sum[N2];
#ifdef LOCAL
debug(sum);
debug(query(1,2*N));
FOR(i,1,N2){
cerr<<Sum[i]<<" ";
}
cend;
#endif
FOR(i,1,N2){
if(A[i]==1) continue;
if(sum<0) sum+=2,A[i]=1;
else A[i]=-1;
}
sum=0;
FOR(i,1,N2){
sum+=A[i];
if(sum<0){
cout<<-1<<"\n";
return;
}
}
FOR(i,1,N2){
if(A[i]==1){
cout<<"(";
}else{
cout<<")";
}
}
cout<<"\n";
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）