C. Sereja and Brackets
题意：
给你一个只包含 '(' 和 ')' 的字符串，由m个询问，每次询问给定一个区间，求区间内 '(' 和 ')' 匹配的个数。
思路：
观察发现每个 ')' 匹配的 ’(’ 的位置是一定的，我们可以将每一个与之匹配的 ‘(’ 的位置保存起来，将询问按照右端点排序。边更新边查询，在区间范围内被标记点的个数即为括号匹配的对数。（因为在存位置时 保存的是与右括号 ‘) ’匹配的左括号 '(' 的位置，更新时是按照右括号添加左括号的位置。所以如果左括号在区间内，则于他相匹配的右括号一定也在区间内）
#include<iostream> #include<algorithm> #include<cstdlib> #include<sstream> #include<cstring> #include<string> #include<bitset> #include<cstdio> #include<string> #include<deque> #include<stack> #include<cmath> #include<queue> #include<set> #include<map> #define mod 1000000007 using namespace std; typedef long long ll; const int maxn = 1e6+10; struct node { int l,r; int id; }q[maxn]; char s[maxn]; int c[maxn],res[maxn],n,m; int pos[maxn]; //记录与 ')' 匹配的 '(' 的位置 stack<int> st; bool cmp(node a,node b) { return a.r<b.r; } int lowbit(int x) { return x&(-x); } void add(int x) { while(x<=n) { c[x]++; x += lowbit(x); } } int ask(int x) { int ans = 0; while(x) { ans += c[x]; x -= lowbit(x); } return ans; } int main() { scanf("%s",s+1); n = strlen(s+1); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id = i; } for(int i=1;i<=n;i++) //保存位置 { if(s[i]=='(') st.push(i); else if(s[i]==')') { if(st.empty()) //没有与他匹配的 pos[i] = n+1; else { pos[i] = st.top(); st.pop(); } } } sort(q+1,q+m+1,cmp); int p = 0; for(int i=1;i<=m;i++) { while(p<q[i].r) { p++; if(s[p]==')') add(pos[p]); //把该位置标记 } res[q[i].id] = ask(q[i].r)-ask(q[i].l-1); } for(int i=1;i<=m;i++) printf("%d\n",2*res[i]); //res[i] 存储的是第 i 个区间匹配的对数，所以输出时要乘2 return 0; }
