CodeTON Round 3 : E. Bracket Cost

まぁまぁの出来の回。
https://codeforces.com/contest/1750/problem/E

問題

括弧列のコストを、以下の作業を繰り返し正しい括弧列にする最小作業数とする。

• 連続部分列を指定し、1つ右にrotateする
• 開き括弧か閉じ括弧を1つ任意の位置に加える。

括弧列が与えられるので、その全部分列に対し、上記コストの総和を求めよ。

解法

まずコストの算出法だが、開き括弧と閉じ括弧の数に差があれば、その分後者のクエリを実行しよう。
また、そのうえでprefixの閉じ括弧数が開き括弧に先行する個数の分だけ、rotateすればよい。

全部分列を考える際、開始位置を走査しながら、終端位置それぞれにおける両コストをBITを使い計算しよう。

int T,N;
string S;
int P[402020];

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,20> num,sum;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		
		FOR(i,N+3) {
			num.add(i,-num(i));
			sum.add(i,-sum(i));
		}
		
		ll ret=0;
		vector<pair<ll,ll>> V;
		ll cur=201010;
		V.push_back({cur,0});
		FOR(i,N) {
			if(S[i]=='(') cur++;
			else cur--;
			V.push_back({cur,i+1});
		}
		sort(ALL(V));
		reverse(ALL(V));
		FORR2(v,i,V) {
			ret+=(sum(N+1)-sum(i))-v*(num(N+1)-num(i));
			sum.add(i,v);
			num.add(i,1);
		}
		V.clear();
		cur=P[N];
		ll sum=cur;
		V.push_back({cur,N});
		for(i=N-1;i>=0;i--) {
			if(S[i]==')') {
				cur--;
			}
			else {
				cur++;
				x=(int)V.size()-1;
				while(x>=0&&V[x].first<=cur) x--;
				if(x==-1) {
					V.clear();
					sum=1LL*cur*(N-i);
				}
				else {
					for(j=x+1;j<V.size();j++) {
						sum+=1LL*(V[j-1].second-V[j].second)*(cur-V[j].first);
					}
					V.resize(x+1);
					
				}
				
			}
			V.push_back({cur,i});
			/*
			cout<<i<<" "<<S[i]<<" "<<cur<<" "<<sum<<" "<<(sum-(N-i)*cur)<<"  :: ";
			FORR2(a,b,V) cout<<a<<":"<<b<<" ";
			cout<<endl;
			*/
			ret+=sum-1LL*(N-i)*cur;
			sum+=cur;
		}
		
		cout<<ret<<endl;
	}
}

まとめ

わりかし手間取ったな。