Codeforces ECR #166 : D. Invertible Bracket Sequences

これはだいぶ典型寄りかな…。
https://codeforces.com/contest/1976/problem/D

問題

正しい括弧列が与えられる。
この部分列のうち、"("と")"を反転したときも、正しい括弧列となるのは何通りか。

解法

f(n) := 先頭n文字における、開き括弧数から閉じ括弧数を引いたもの

とすると反転する区間が[L,R)の両端の場合、f(L)=f(R)でなければならない。
そこで、f(n)の値が一致するnをまとめて処理する。
SegTreeを使えば区間内に反転させると閉じ括弧数が超過するかどうかわかるので、尺取り法の要領でLに対しRをどこまで伸ばせるか判定できる。

int T,N;
string S;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;
int C[202020];
vector<int> V[404020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		C[0]=0;
		V[C[0]].push_back(C[0]);
		FOR(i,N) {
			if(S[i]=='(') C[i+1]=C[i]+1;
			else C[i+1]=C[i]-1;
			st.update(i+1,C[i+1]);
			V[C[i+1]].push_back(i+1);
		}
		
		ll ret=0;
		for(i=0;i<=N;i++) {
			for(int L=0,R=0;L<V[i].size();L++) {
				while(R<V[i].size()&&st.getval(V[i][L],V[i][R]+1)<=2*i) R++;
				ret+=R-L-1;
			}
			V[i].clear();
		}
		cout<<ret<<endl;
		
		
	}
}

まとめ

どっかで似たような問題出てそうだな。