PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Tia Shi Wei
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
You are given a bracket sequence A of length N and Q queries of the following form:
L R : You are given two integers L and R (1 \le L \le R \le N). Find the number of pairs (X, Y), where L \le X \le Y \le R, such that after removing the substring A_{[X,Y]} from A_{[L,R]}, the substring A_{[L , R]} becomes a balanced bracket sequence.
In other words, for a given (L, R), find the number of pairs (X, Y), such that the sequence A_L \ldots A_{X-1}A_{Y+1}\ldots A_R is a balanced bracket sequence.
EXPLANATION:
Due to the nature of the constraints (N \le 3000, Q \le 2 \cdot 10^6), our best bet is to precompute the answer for all pairs (L, R) beforehand. We will use dynamic programming to do this.
For all i such that A_i = (, let nxt_i be the smallest index j > i such that A_{[i,j]} is a balanced bracket sequence. Similarly, for all i such that A_i = ), let prv_i be the largest index j < i such that A_{[j, i]} is a balanced bracket sequence. The process of initializing nxt and prv is not hard: we use a stack to run through A once. Observe that among all ranges [i, nxt_i] and [prv_j, j], any two such ranges must either be completely disjoint (no overlap), or one completely overlaps the other one (this is due to the properties of the stack process).
Now we are ready to compute the answer. Denote dp_{l, r} as the answer for the query (l, r) (i.e. the number of pairs (x, y) such that the sequence A_l \ldots A_{x-1}A_{y+1}\ldots A_r is a balanced bracket sequence).
We analyze the simplest case: A_l = (, A_r = ), and l < nxt_l < prv_r < r. There are two cases:
- The chosen removal range [x, y] doesn’t touch either [l, nxt_l] or [prv_r, r]. We can solve this case through inclusion-exclusion:
- The chosen range doesn’t touch [l, nxt_l]. Since A_{[l, nxt_l]} is a balanced bracket sequence already, it must mean that (x, y) turns A_{[nxt_l + 1, r]} into a balanced bracket sequence. Therefore, the number of (x, y) pairs in this subcase is dp_{nxt_l + 1, r}.
- The chosen range doesn’t touch [prv_r, r]. With similar reasoning, the answer in this subcase is dp_{l, prv_r - 1}.
- The chosen range doesn’t touch both [l, nxt_l] and [prv_r, r]. With similar reasoning, the answer in this subcase is dp_{nxt_l + 1, prv_r - 1}.
Therefore, the answer in this case is dp_{nxt_l + 1, r} + dp_{l, prv_r - 1} - dp_{nxt_l + 1, prv_r - 1}.
- The chosen removal range [x, y] touches both [l, nxt_l] and [prv_r, r]. Note that in this case, after removing [x, y], it must be that A_l and A_r is matched with each other in the new balanced bracket sequence. Similarly, any range [x, y] to make A_l and A_r matched with each other must touches both [l, nxt_l] and [prv_r, r] (if not, either A_l will be matched with A_{nxt_l}, or A_r will be matched with A_{prv_r}). This means the answer in this case is the number of ways to choose [x, y] such that A_l and A_r is matched with each other, which is equivalent to the number of ways to turn the range A_{[l + 1, r - 1]} into a balanced bracket sequence, which is dp_{l + 1, r - 1}.
Combining with the trivial case of removing the whole range, we arrive at the recursive formula dp_{l, r} = 1 + dp_{nxt_l + 1, r} + dp_{l, prv_r - 1} - dp_{nxt_l + 1, prv_r - 1} + dp_{l + 1, r - 1}. It turns out that with careful initialization of nxt and prv, this formula is also the same for all cases; proof is left as exercise for the readers 
TIME COMPLEXITY:
Time complexity is O(N^2 + Q) per test case.
SOLUTION:
Setter's Solution
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 3005
#define MAXQ 2000005
struct Qry {
int l, a, y, x, i;
bool operator< (const Qry &o) const {
if (y == o.y) return i < o.i; // updates go first
return y < o.y;
}
};
int n, q;
string s;
int a[MAXN];
vector<Qry> qrys[MAXN * 2];
int lft[MAXN], rht[MAXN];
int ans[MAXQ];
int fw[MAXN * 2];
void incre(int i, int x) {
for (; i <= 2 * n + 5; i += i & -i) fw[i] += x;
}
int qsm(int i) {
int res = 0;
for (; i > 0; i -= i & -i) res += fw[i];
return res;
}
int qsm(int s, int e) {
return qsm(e) - qsm(s - 1);
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> q;
cin >> s;
REP (i, 1, n + 1) {
a[i] = s[i - 1] == '(' ? 1 : -1;
a[i] += a[i - 1];
}
REP (i, 1, n + 1) {
lft[i] = n;
REP (j, i, n + 1) {
if (a[j] - a[i - 1] < 0) {
lft[i] = j;
break;
}
}
}
RREP (i, n, 1) {
rht[i] = 1;
RREP (j, i, 1) {
if (a[i] - a[j - 1] > 0) {
rht[i] = j;
break;
}
}
}
REP (i, 0, q) {
int l, r; cin >> l >> r;
qrys[a[r] - a[l - 1] + n].pb((Qry) {l, lft[l], rht[r] - 1, -1, i});
qrys[a[r] - a[l - 1] + n].pb((Qry) {l, lft[l], r, 1, i});
cerr << a[r] - a[l - 1] << ": " << l << ' ' << lft[l] << ' ' << rht[r] - 1 << ' ' << -1 << '\n';
cerr << a[r] - a[l - 1] << ": " << l << ' ' << lft[l] << ' ' << r << ' ' << 1 << '\n';
}
REP (i, 1, n + 1) {
REP (j, 1, i + 1) {
qrys[a[i] - a[j - 1] + n].pb((Qry) {j, j, i, 0, -1});
cerr << a[i] - a[j - 1] << ": " << j << ' ' << i << '\n';
}
}
REP (g, 0, 2 * n + 1) {
sort(ALL(qrys[g]));
for (auto [l, a, y, x, i] : qrys[g]) {
if (i == -1) {
incre(l, 1);
} else {
ans[i] += qsm(l, a) * x;
}
}
for (auto [l, a, y, x, i] : qrys[g]) {
if (i == -1) {
incre(l, -1);
}
}
}
REP (i, 0, q) {
cout << ans[i] << '\n';
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3001;
int n,q;
int a[N];
int f[2*N];
int jl[N],jr[N];
ll dp[N][N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> q;
for(int i=0; i<=2*n ;i++) f[i]=-1;
for(int i=0; i<=n ;i++){
jl[i]=-1;jr[i]=n+1;
}
a[0]=n;
f[n]=0;
for(int i=1; i<=n ;i++){
char c;cin >> c;
if(c=='(') a[i]=a[i-1]+1;
else a[i]=a[i-1]-1;
if(f[a[i]]!=-1){
jr[f[a[i]]]=i;
jl[i]=f[a[i]];
}
f[a[i]]=i;
}
for(int r=1; r<=n ;r++){
dp[r][r]=0;
for(int l=r-1; l>=0 ;l--){
dp[l][r]=1;
bool cl=(a[l+1]>a[l] && jr[l]<=r);
bool cr=(a[r-1]>a[r] && jl[r]>=l);
if(cl) dp[l][r]+=dp[jr[l]][r];
if(cr) dp[l][r]+=dp[l][jl[r]];
if(cl && cr && jr[l]<=jl[r]) dp[l][r]-=dp[jr[l]][jl[r]];
if(a[l+1]>a[l] && a[r-1]>a[r]){
dp[l][r]+=dp[l+1][r-1];
}
//cout << l << ' ' << r << ' ' << dp[l][r] << endl;
}
}
for(int i=1; i<=q ;i++){
int l,r;cin >> l >> r;
cout << dp[l-1][r] << '\n';
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
string s; cin >> s;
vector<int> nxt(n, n), prv(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
st.push_back(i);
} else if (!st.empty()) {
nxt[st.back()] = i;
prv[i] = st.back();
st.pop_back();
}
}
vector<vector<int>> dp(n, vector<int>(n));
for (int l = n - 1; l >= 0; l--) {
for (int r = l; r < n; r++) {
dp[l][r] = 1;
int nl = nxt[l], pr = prv[r];
if (nl < r) {
dp[l][r] += dp[nl + 1][r];
}
if (pr > l) {
dp[l][r] += dp[l][pr - 1];
}
if (nl + 1 <= pr - 1) {
dp[l][r] -= dp[nl + 1][pr - 1];
}
if (s[l] == '(' && s[r] == ')') {
dp[l][r] += dp[l + 1][r - 1];
}
}
}
while (q--) {
int l, r; cin >> l >> r; l--; r--;
cout << dp[l][r] << '\n';
}
}