Bracket Substring Queries
Autumn Tournament (2020)
Submission name: skobi.cpp
Problem summary
For each requested inclusive substring of a parenthesis string, decide whether it is a correctly nested bracket sequence. Print 1 for a valid sequence and 0 otherwise.
Source clarification. The statement’s informal matching definition omits an explicit prefix-order condition. The official editorial confirms ordinary correct nesting, including the no-negative-prefix requirement. This solution follows that intended interpretation. Editorial: https://infos.infosbg.com/files/Contests/ETI/2020/C/analyses/skobi_analysis.docx
Input
N, the length-N string, T, then T pairs L R with 1-based inclusive indices.
Output
One 0 or 1 per query.
Constraints
2 ≤ N ≤ 100000; 1 ≤ T ≤ 100000; 1 ≤ L ≤ R ≤ N.
Worked example
Original statement sample.
Input
5 )()() 3 1 3 2 3 2 5
Output
0 1 1
Solution analysis
- Define balance[i] as the number of opening brackets minus closing brackets in the first i characters, with balance[0]=0. A substring [L,R] has equal counts exactly when balance[R]=balance[L−1]. This alone is insufficient: )( has equal counts but closes before it opens.
- The second condition is that no prefix within [L,R] falls below balance[L−1]. For every prefix index i, precompute nextLower[i], the first later index with a strictly smaller balance. Scanning from right to left with a monotonic stack removes indices whose balances are at least the current balance, leaving the nearest strictly smaller one at the top.
- A query is valid exactly when the two endpoint balances agree and nextLower[L−1]>R. For )()(), the balances are 0,−1,0,−1,0,−1. Query[1,3] fails equal counts. Query[2,3] starts at balance−1, ends at−1 and never falls below−1; [2,5] likewise contains two valid pairs.
Why it works
The balance test is the standard necessary and sufficient characterization of correct nesting: totals match and no prefix has too many closing brackets. The monotonic stack gives the first location violating the second condition. Equal-or-larger candidates can be removed because the current index is nearer and no larger for any earlier query. Thus both tests answer each substring exactly.
Watch out. Use balance[L−1], not balance[L], and include prefix index 0. Pop equal balances as well as larger ones: only a strictly lower balance invalidates a query. Equal counts do not by themselves imply correct nesting.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
string brackets;
cin>>brackets;
vector<int>balance(n+1,0);
for(int i=1;i<=n;i++){
balance[i]=balance[i-1]+(brackets[i-1]=='('?1:-1);
}
vector<int>nextLower(n+1,n+1);
vector<int>pending;
for(int i=n;i>=0;i--){
// Keep the nearest candidate with a strictly smaller balance.
while(!pending.empty()&&balance[pending.back()]>=balance[i]){
pending.pop_back();
}
if(!pending.empty()){
nextLower[i]=pending.back();
}
pending.push_back(i);
}
int queries;
cin>>queries;
while(queries--){
int left;
int right;
cin>>left>>right;
bool valid=balance[right]==balance[left-1]&&nextLower[left-1]>right;
cout<<(valid?1:0)<<'\n';
}
}