Contest Duration: - (local time) (100 minutes) Back to Home

## F - Parenthesis Checking Editorial by en_translator

First we consider how to determine if a string $$S$$ of length $$M$$ is a correct parenthesis sequence. Let $$A=(A_1,A_2,\ldots,A_M)$$ be the sequence of integers obtained by replacing ( in $$S$$ with $$+1$$ and ) with $$-1$$m and $$B=(B_0,B_1,\ldots,B_M)$$ be the cumulative sums of the prefixes. For example, if $$S=$$(()), then $$A=(1,1,-1,-1)$$ and $$B=(0,1,2,1,0)$$. Then, $$S$$ is a correct parenthesis sequence if and only if:

$$B_M=0$$ and the minimum element of $$B$$ is $$0$$.

The queries in the original problem are queries for segments, so we consider using a segment tree. Each node of the segment tree will manage the minimum element of $$B$$ and $$B_M$$ for the corresponding to contiguous substring. From these information, two segments can be merged in an $$O(1)$$ time, so the problem can be solved using a segment tree capable of one-element updates and contiguous-elements derivations.

Alternatively, we can manage $$B$$ it self with a segment tree, using a segment tree capable of contiguous-elements addition and contiguous-elements minimum value derivations.

Sample code (C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

pair<int, int> op(pair<int, int> a,pair<int, int> b){
return make_pair(min(a.first, a.second + b.first), a.second + b.second);
}
pair<int, int> e(){
return make_pair(0, 0);
}

int main(){
int n, q; cin >> n >> q;
string s; cin >> s;
vector<pair<int, int>> v(n);
for(int i = 0; i < n; i++){
if(s[i] == '(') v[i] = make_pair(0, 1);
else v[i] = make_pair(-1, -1);
}
segtree<pair<int, int>, op, e> seg(v);
for(int i = 0; i < q; i++){
int t, l, r; cin >> t >> l >> r; l--; r--;
if(t == 1){
swap(v[l], v[r]);
seg.set(l, v[l]);
seg.set(r, v[r]);
}
else{
if(seg.prod(l, r + 1) == make_pair(0, 0)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
}


Sample code (C++) (Alternative solution)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int op(int a, int b){ return min(a, b); }
int e(){ return 1001001001; }
int mapping(int f, int x){ return f+x; }
int composition(int f, int g){ return f+g; }
int id(){ return 0; }

int main(){
int n, q; cin >> n >> q;
string s; cin >> s;
vector<int> v(n + 1);
for(int i = 0; i < n; i++){
if(s[i] == '(') v[i + 1] = v[i] + 1;
else v[i + 1] = v[i] - 1;
}
lazy_segtree<int, op, e, int, mapping, composition, id> seg(v);
for(int i = 0; i < q; i++){
int t, l, r; cin >> t >> l >> r;
if(t == 1){
if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2);
if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2);
swap(s[l - 1], s[r - 1]);
}
else{
if(seg.prod(l - 1, r + 1) == seg.get(l - 1) && seg.get(l - 1) == seg.get(r)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
}


posted:
last update: