Codeforces #765 : Div2 E2. Cats on the Upgrade

ようやく2022年の通常回に。
https://codeforces.com/contest/1625/problem/E2

問題

括弧とドットで構成される文字列がある。
この文字列がシンプルかつ正常な括弧列であるとは、

• 先頭と末尾はドットではない
• ドットを取り除くと、正常な括弧列である

文字列Sが与えられるので、以下のクエリに答えよ。

• 文字列の区間(先頭が開き括弧、末尾が閉じ括弧、間がドット)が与えられるので、その部分をすべてドットで上書きする。
• 文字列の区間が与えられるので、その部分列のうち正常な括弧列の個数を答える。

解法

文字列を木構造に置き換える。
開き括弧に対し、それを囲う1段上のレベルの開き括弧の位置を求めておこう。
BITを使い、各開き括弧に対し、1段下のレベルの開き括弧・閉じ括弧の対応法の個数を保持しておく。
これをクエリ毎に更新していくとよい。

int N,M;
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<ll,21> bt,child;

int T[909090];
int P[909090];
vector<int> C[909090];
int start[909090];
ll num[909090];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	int o=count(ALL(S),'(');
	int c=count(ALL(S),')');
	S=string(c,'(')+S+string(o,')');
	vector<int> st={0};
	int cur=0;
	
	FOR(i,S.size()) {
		x=st.back();
		if(S[i]=='(') {
			C[x].push_back(i+1);
			P[i+1]=x;
			st.push_back(i+1);
		}
		else {
			T[i+1]=x;
			T[x]=i+1;
			num[x]=C[x].size();
			bt.add(x,num[x]*(num[x]+1)/2);
			start[x]=cur;
			cur+=C[x].size();
			st.pop_back();
		}
		child.add(i,1);
	}
	
	while(M--) {
		int L,R;
		cin>>i>>L>>R;
		L+=c;
		R+=c;
		if(i==1) {
			assert(T[L]==R);
			x=P[L];
			bt.add(x,-num[x]*(num[x]+1)/2);
			num[x]--;
			bt.add(x,num[x]*(num[x]+1)/2);
			
			i=lower_bound(ALL(C[x]),L)-C[x].begin();
			child.add(start[x]+i,-1);
		}
		else {
			ll pat=bt(R)-bt(L-1);
			x=P[L];
			i=lower_bound(ALL(C[x]),L)-C[x].begin();
			j=lower_bound(ALL(C[x]),R)-C[x].begin();
			ll alive=child(start[x]+j-1)-child(start[x]+i-1);
			pat+=alive*(alive+1)/2;
			
			cout<<pat<<endl;
		}
	}
	
}

まとめ

これすごい簡単というわけでもないし、コードもそこまで短くないんだけど、upsolve数が妙に多いな。