CODE FESTIVAL 2014 エキシビジョン : B - カッコつけ

これは時間切れだなぁ。
http://code-festival-2014-exhibition-open.contest.atcoder.jp/tasks/code_festival_exhibition_b

問題

開きかっこと閉じかっこで構成された長さLの文字列Sがあるとする。
文字列Sのかっこ悪さとは、開きかっこと閉じかっこの対応が取れるようにするため、削除しないといけない文字の数とする。

初期文字列Sが与えられるので、以下の４種で構成される計Q個のクエリに答えよ。

• yが与えられるので、S[y]に'('を挿入
• yが与えられるので、S[y]に')'を挿入
• yが与えられるので、S[y]を削除
• y,zが与えられるので、S[y..z]のかっこ悪さを回答

解法

文字列のかっこ悪さは以下のように求められる。
括弧の対応関係の変数を管理する。
文字を先頭から順に見て、開きかっこなら+1、閉じかっこなら-1する。
また、途中で変数の最小値を覚えておく。

最終的な変数値をdif、最小値をmindとする。
最後、dif個分開きかっこが多いので、開きかっこをどこかでdif個分削らな避ければならない。
また、途中閉じかっこの方が多いケースがmind回あるので、その分閉じかっこを減らさなければならない。
さらに閉じかっこを減らし多分difが増加することも考慮すると、結局dif+mind*2がかっこ悪さとなる。

上記前提をもとにクエリに回答する。
方針としては平方分割である。
SをO(√L)個程度に分割し、それぞれのdif,mind値を更新しておく。

挿入・削除系クエリに関しては、分割した個々の文字列に対して行うことで１回あたりコストをO(√L)に抑える。
挿入クエリがたまると、特定の分割文字列の長さが長くなってしまうので、時々長さを均等に鳴らしておく。

かっこ悪さを問うクエリにおいては、個々の分割した文字列のdif,mind値を用いることでO(√L)で回答する。

string SS[500];
int mind[500];
int dif[500];
int Q;

pair<int,int> dodo(int cur,int y,int z) {
	int i;
	int mi=0,dif=0;
	for(i=y;i<z;i++) {
		if(SS[cur][i]=='(') dif++;
		else dif--, mi=max(mi,-dif);
	}
	return make_pair(mi,dif);
}

void rebuild2(int cur) {
	pair<int,int> p = dodo(cur,0,SS[cur].size());
	mind[cur]=p.first;
	dif[cur]=p.second;
}

void rebuild() {
	string s;
	int i;
	FOR(i,500) s+=SS[i];
	FOR(i,500) {
		if(s.size()<=i*500) SS[i]="";
		else if(s.size()>=(i+1)*500) SS[i]=s.substr(i*500,500);
		else SS[i]=s.substr(i*500);
		rebuild2(i);
	}
}


void solve() {
	int i,j,k,l,r,x,y,z; string s;

	cin>>Q>>SS[0];
	rebuild();
	int ad=0;
	while(Q--) {
		cin>>s>>y>>z;
		y--;
		if(s[0]=='(' || s[0]==')') {
			FOR(i,500) {
				if(y<=SS[i].size()) break;
				y-=SS[i].size();
			}
			SS[i].insert(y,s.c_str());
			if(++ad>=1000) rebuild(), ad=0;
			else rebuild2(i);
		}
		if(s[0]=='D') {
			FOR(i,500) {
				if(y<SS[i].size()) break;
				y-=SS[i].size();
			}
			SS[i].erase(SS[i].begin()+y);
			rebuild2(i);
		}
		if(s[0]=='Q') {
			int iy,iz;
			FOR(iy,500) {
				if(y<SS[iy].size()) break;
				y-=SS[iy].size();
			}
			FOR(iz,500) {
				if(z<=SS[iz].size()) break;
				z-=SS[iz].size();
			}
			
			if(iy==iz) {
				pair<int,int> p=dodo(iy,y,z);
				cout << p.first+(p.second+p.first) << endl;
			}
			else {
				int di=0,mi=0;
				pair<int,int> p = dodo(iy,y,SS[iy].size());
				mi=p.first;
				di=p.second+p.first;
				for(i=iy+1;i<iz;i++) {
					p=make_pair(mind[i],dif[i]);
					if(p.first>di) mi+=p.first-di, di+=p.second+(p.first-di);
					else di+=p.second;
				}
				p=dodo(iz,0,z);
				if(p.first>di) mi+=p.first-di, di+=p.second+(p.first-di);
				else di+=p.second;
				
				cout << mi+di << endl;
			}
			
		}
	}
	
}

まとめ

平衡木でもっと高速に解けるらしいが理解していない…。