树状数组求区间内范围个数。。。。
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
A subsequence of length |x| of string s?=?s1s2... s|s| (where |s| is the length of string s) is string x?=?sk1sk2... sk|x| (1?≤?k1?<?k2?<?...?<?k|x|?≤?|s|).
A correct bracket sequence is 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 ?()?.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1001000;
int tr1[maxn],tr2[maxn],tot;
char str[maxn];
int lowbit(int x)
{
return x&(-x);
}
void Add(int tr[],int n)
{
while(n<maxn)
{
tr[n]++;
n+=lowbit(n);
}
}
int Sum(int tr[],int x)
{
int sum=0;
while(x>0)
{
sum+=tr[x];
x-=lowbit(x);
}
return sum;
}
struct Interval
{
int l,r,len,ans,id;
}q[maxn],a[maxn];
bool cmp1(Interval a,Interval b)
{
if(a.len!=b.len)
{
return a.len<b.len;
}
else return a.l<b.l;
}
bool cmpID(Interval a,Interval b)
{
return a.id<b.id;
}
int st[maxn],pop=-1,m,qt;
int main()
{
scanf("%s",&str);
int len=strlen(str);
for(int i=0;i<len;i++)
{
if(str[i]==‘(‘)
{
st[++pop]=i+1;
}
else
{
if(pop>=0)
{
a[tot].l=st[pop--];
a[tot].r=i+1;
a[tot].len=a[tot].r-a[tot].l+1;
tot++;
}
}
}
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
q[qt].l=l,q[qt].r=r;
q[qt].len=r-l+1,q[qt].id=i;
qt++;
}
sort(q,q+qt,cmp1);
sort(a,a+tot,cmp1);
int pos=0;
for(int i=0;i<m;i++)
{
while(pos<tot&&a[pos].len<=q[i].len)
{
Add(tr1,a[pos].l);Add(tr2,a[pos].r);
pos++;
}
q[i].ans=Sum(tr2,q[i].r)-Sum(tr1,q[i].l-1);
}
sort(q,q+qt,cmpID);
for(int i=0;i<qt;i++)
{
printf("%d\n",q[i].ans*2);
}
return 0;
}