Codeforces 380C Sereja and Brackets(线段树）

题目链接：Codeforces 380C Sereja and Brackets

题目大意：给出一串括号，然后m次询问，问说a，b之间有多少个括号匹配。

解题思路：首先遍历一遍，将每个位置的从1到当前位置的有效右括号数和没有用到的左括号数记录下来；然后每次查询a，b区间，即为t = r[b] - r[a-1](有效右括号数），但是要注意，这些有效右括号的匹配左括号可能不在区间上，所以要减去l[a-1]（未用到的左括号数），但是又有可能[1,a-1]中未用到的左括号和[b+1,len]中的右括号相匹配，所以要加上min(l[a~b]),这不用到线段树查询最小值。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 1000005;

struct node {
	int dl, dr, v;
}s[N*3];

int n, r[N], l[N], len;
char str[N];

int build (int x, int y, int f) {
	s[f].dl = x, s[f].dr = y;

	if (x == y) return s[f].v = l[x];

	int mid = (x + y) / 2;
	return s[f].v = min(build(x, mid, 2 * f), build(mid+1, y, 2*f+1));
}

int query(int x, int y, int f) {
	if (x == s[f].dl && y == s[f].dr) return s[f].v;

	int mid = (s[f].dl + s[f].dr) / 2;
	if (mid >= x && mid < y) return min(query(x, mid, 2*f), query(mid+1, y, 2*f+1));
	else if (mid >= x && mid >= y) return query(x, y, 2*f);
	else return query(x, y, 2*f+1);
}

void solve () {
	memset(r, 0, sizeof(r));
	memset(l, 0, sizeof(l));
	len = strlen(str);
	int tmp = 0;
	for (int i = 1; i <= len; i++) {
		r[i] = r[i-1];

		if (str[i-1] == ‘(‘) tmp++;
		else if (tmp) {
			r[i]++; tmp--;
		}
		l[i] = tmp;
	}
	build(1, len, 1);
}

int main () {
	gets(str);
	solve ();

	int a, b;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a, &b);
		a = min(len, a); b = min(len, b);
		printf("%d\n", (r[b] - r[a-1] - max(l[a-1] - query(a, b, 1), 0)) * 2);
	}
	return 0;
}

Codeforces 380C Sereja and Brackets(线段树）

原文：http://blog.csdn.net/keshuai19940722/article/details/19014821