Codeforces #223 Div1. C. Sereja and Brackets

本番内にうまく解けず。
http://codeforces.com/contest/380/problem/C

問題

括弧だけで構成された文字列Sが与えられる。
ここで、L[i],R[i]で構成されるクエリが与えられる。
各クエリは、S[L[i]]～S[R[i]]の部分文字列のうち、最長のcorrect bracket sequenceの文字列を答えるものである。

M個のクエリに答えよ。

解法

本番は最初部分文字列はcontiguousだと勘違いして時間をロスした。

まずクエリを先に全部読み、R[i]別にまとめておく。
次に文字列を先頭から読み、スタックを用いて以下のように処理していく。

• 左括弧が出たらその位置をpush
• 右括弧が出たらスタックからpop。Bit Index Tree中、スタックから取得した左括弧の位置に対応する位置をインクリメントする。

その際、処理した文字列の位置をR[i]とするクエリを適宜処理する。
各処理では、BIT中L[i]以上の値の総和を取り２倍すればよい。
これによりL[i]～R[i]中に含まれる括弧の対応の数の総和を取れる。

string S;
int N,M;
int ML[1000010];
vector<pair<int,int> > Q[1000100];
int ret[1000100];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,21> bt;


void solve() {
	int f,i,j,k,x,y,l,r;
	
	cin>>S;
	N=S.size();
	cin>>M;
	FOR(i,M) {
		cin>>l>>r;
		Q[r-1].push_back(make_pair(l-1,i));
	}
	
	stack<int> ST;
	y=0;
	FOR(i,N) {
		if(S[i]=='(') ST.push(i);
		else if(!ST.empty()) {
			ML[ST.top()]=i;
			bt.update(ST.top()+1,1);
			ST.pop();
			y++;
		}
		FOR(j,Q[i].size()) ret[Q[i][j].second] = y-bt.total(Q[i][j].first);
	}
	FOR(i,M) _P("%d\n",2*ret[i]);
}

まとめ

クエリ順の並べ替えやBIT等、CFにおける定番ネタの範囲で解ける問題。
これは本番に解きたかった。