题目链接：
Sereja has a bracket sequences1,s2,…,sn, or, in other words, a stringsof lengthn, consisting of characters "(" and ")".
Sereja needs to answermqueries, each of them is described by two integersli,ri(1≤li≤ri≤n). The answer to thei-th query is the length of the maximum correct bracket subsequence of sequencesli,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 characterss1,s2,…,sn(1≤n≤106)without any spaces. Each character is either a "(" or a ")". The second line contains integerm(1≤m≤105)— the number of queries. Each of the nextmlines contains a pair of integers. Thei-th line contains integersli,ri(1≤li≤ri≤n)— the description of thei-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
())(())(())(71 12 31 21 128 125 112 10
output
00210466
Note
Asubsequenceof length|x|of strings=s1s2…s|s|(where|s|is the length of strings) is stringx=sk1sk2…sk|x|(1≤k1<k2<…<k|x|≤|s|).
Acorrect bracket sequenceis a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
For the third query required sequence will be ().
For the fourth query required sequence will be ()(())(()).
题意：
给出一个含‘ ( ’ ，，‘ ) ‘ 的字符串，
然后给出一个询问区间，去这个区间里完整匹配的（）的数目！一个（）的答案为2！
PS:
我们可以用栈把每个’ （ ‘的下标存起来！然后再扫一遍’ ）‘！用树状数组维护一下即可！
代码如下：#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <iostream>#include <stack>using namespace std;#define maxn 1000017#define maxm 100017using namespace std;struct node{int l, r;int id;} q[maxm];char s[maxn];int c[maxn];int ans[maxm];stack<int> st;int len;int Lowbit(int x) // 2^k{return x&(-x);}void update(int i, int x)//i点增量为x{while(i <= len){c[i] += x;i += Lowbit(i);}}int sum(int x)//区间求和 [1,x]{int ans = 0;while(x){ans += c[x];x -= Lowbit(x);}return ans;}bool cmp(node a, node b){return a.r < b.r;}int main(){int m;while(~scanf("%s",s)){int pos = 1;memset(c, 0, sizeof(c));while(!st.empty()){st.pop();}len = strlen(s);scanf("%d",&m);for(int i = 0; i < m; i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id = i;}sort(q, q+m, cmp);for(int i = 0; i < m; i++){for(int j = pos; j <= q[i].r; j++){if(s[j-1] == '('){st.push(j);}else if(s[j-1] == ')'){if(!st.empty()){int tt = st.top();update(tt, 2);st.pop();}}}pos = q[i].r+1;ans[q[i].id] = sum(q[i].r) – sum(q[i].l-1);}for (int i = 0; i < m; i++){printf("%d\n", ans[i]);}}return 0;}/*())(())(())(71 11 22 32 105 111 128 12*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
在旅途中，我遇见了你，你我相识是缘分！看着你手中的戒指，
