本文主要是介绍Codeforces 380C - Sereja and Brackets (线段树括号匹配)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Sereja has a bracket sequence s1, s2, ..., sn, or, in other words, a string s of length n, consisting of characters "(" and ")".
Sereja needs to answer m queries, each of them is described by two integers li, ri (1 ≤ li ≤ ri ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence sli, sli + 1, ..., sri. Help Sereja answer all queries.
You can find the definitions for a subsequence and a correct bracket sequence in the notes.
The first line contains a sequence of characters s1, s2, ..., sn (1 ≤ n ≤ 106) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains a pair of integers. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n) — the description of the i-th query.
Print the answer to each question on a single line. Print the answers in the order they go in the input.
())(())(())( 7 1 1 2 3 1 2 1 12 8 12 5 11 2 10
0 0 2 10 4 6 6
题意：给定一组括号，以下有m次询问，问一个区间有几个括号匹配。
思路：线段树，在向上传递值的时候，左区间的左括号和右区间的右括号能组成一个新括号传递上去。
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 1000005;int n, m;
char str[N];struct Tree {int l, r, lv, rv, sum;Tree operator + (const Tree &a) {Tree h;h.sum = sum + a.sum; h.lv = lv + a.lv; h.rv = rv + a.rv;int num1 = min(lv, a.rv); h.sum += num1 * 2; h.lv -= num1; h.rv -= num1;return h;}
}st[3 * N];Tree build(int l, int r, int id) {if (l == r) {if (str[l] == '(') {st[id].lv = 1; st[id].rv = 0; st[id].sum = 0;}else {st[id].lv = 0; st[id].rv = 1; st[id].sum = 0;}st[id].l = l; st[id].r = r;}else {int mid = (l + r) / 2;st[id] = build(l, mid, id * 2) + build(mid + 1, r, id * 2 + 1);st[id].l = l; st[id].r = r;}return st[id];
}Tree Query(int l, int r, int id) {if (l == st[id].l && r == st[id].r)return st[id];int mid = (st[id].l + st[id].r) / 2;if (l <= mid && r > mid)return Query(l, mid, 2 * id) + Query(mid + 1, r, 2 * id + 1);else if (l <= mid && r <= mid) {return Query(l, r, 2 * id);}else {return Query(l, r, 2 * id + 1);}
}void init() {scanf("%s%d", str + 1, &m);n = strlen(str + 1);build(1, n, 1);int l, r;while (m--) {scanf("%d%d", &l, &r);printf("%d\n", Query(l, r, 1).sum);}
}int main() {init();return 0;
}
这篇关于Codeforces 380C - Sereja and Brackets (线段树括号匹配)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
