yukicoder : No.1802 Range Score Query for Bracket Sequence

適度な解き味で良かった。
https://yukicoder.me/problems/no/1802

問題

左右対称な括弧列とは、正整数個の"("のあとに同数の")"が続く文字列をいう。
文字列sのスコアとは、s中における最長の左右対称な括弧列を取り除く処理を繰り返したとき、処理を行える最大回数を意味する。

今"("")"で構成された文字列Sが与えられる。
以下のクエリに順次答えよ。

• Sの指定された1文字を、"("と")"で入れ替える
• Sの部分文字列S[L...R]のスコアを答える

解法

sのスコアを考えてみると、文字列中の"()"の数に相当する。
そこで、BITを用いて"()"が登場するindexの個数の合計を高速にとれるようにしておくと後者のクエリをO(log|S|)で処理できる。
前者のクエリもBITの2要素の値を更新するだけなので、やはりO(log|S|)で処理できる。

int N,Q;
string S;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	FOR(i,N-1) {
		if(S[i]=='('&&S[i+1]==')') bt.add(i,1);
	}
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x;
			x--;
			if(x&&S[x-1]=='('&&S[x]==')') bt.add(x-1,-1);
			if(x+1<N&&S[x]=='('&&S[x+1]==')') bt.add(x,-1);
			if(S[x]=='(') S[x]=')';
			else S[x]='(';
			if(x&&S[x-1]=='('&&S[x]==')') bt.add(x-1,1);
			if(x+1<N&&S[x]=='('&&S[x+1]==')') bt.add(x,1);
		}
		else {
			int L,R;
			cin>>L>>R;
			L--;
			cout<<bt(R-2)-bt(L-1)<<endl;
			
		}
	}
}

まとめ

"()"を数えればよい、と気づくとあとは易しい。