Codeforces 380C - 세그먼트 트리 괄호 일치

C. Sereja and Brackets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
Input
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.
Output
Print the answer to each question on a single line. Print the answers in the order they go in the input.
Sample test(s)
input

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

output

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
", Query(l, r, 1).sum);
	}
}

int main() {
	init();
	return 0;
}