题目大意：
给定一个括号序列，每个’(‘和右边的’)’匹配，如()(())就是一个合法的序列，()))((就是一个不合法的序列，问最少在最左边添加几个’(‘和在最右边添加几个’)’
解题思路：
用线段树维护lk和rk
lk[i]表示第i个节点多出多少左括号(需要多少右括号) rk[i]表示第i个节点需要多少左括号(多出多少右括号) 然后每次查询要用log n左右的时间，然后m个操作共O(m · log (n))源程序：
#include#include #include #define ls now<<1#define rs now<<1|1#define N 800000using namespace std;int ans1,ans2,n,m,x,y,l[N],r[N],lk[N],rk[N];char check[7],c[150001];void read(int &tot){ tot=0; char c=getchar(); while (!isdigit(c)) c=getchar(); while (isdigit(c)) tot=tot*10+c-48,c=getchar();}void write(int x){ if(x>9) write(x/10);putchar(x%10+48); return;}void writel(int x) {write(x);putchar(32);}void writeln(int x) {write(x);putchar(10);}void query(int now,int lf,int rt)//查询{ if (lf==l[now]&&rt==r[now]) { ans1+=max(rk[now]-ans2,0);//总共需要ans1个左括号 ans2=lk[now]+max(ans2-rk[now],0);//ans2个右括号 return; } int mid=(l[now]+r[now])>>1; if (rt<=mid) query(ls,lf,rt); else if (lf>mid) query(rs,lf,rt); else{ query(ls,lf,mid); query(rs,mid+1,rt); }//往下面查询}void change(int now,int x)//修改{ if (l[now]!=r[now]) { int mid=(l[now]+r[now])>>1; if (x<=mid) change(ls,x); else if (x>mid) change(rs,x); rk[now]=rk[ls]+max(rk[rs]-lk[ls],0);//上传 lk[now]=lk[rs]+max(lk[ls]-rk[rs],0);//上传 } else { if (lk[now]==0) lk[now]=1,rk[now]=0; else lk[now]=0,rk[now]=1; }}void build(int now,int left,int right){ //建树 l[now]=left;r[now]=right; if (left==right){ lk[now]=(c[left]=='(')?1:0;//lk是多余的 rk[now]=1-lk[now];//rk是需要的 return; } build(ls,left,(left+right)>>1); build(rs,((left+right)>>1)+1,right); rk[now]=rk[ls]+max(rk[rs]-lk[ls],0);//上传 lk[now]=lk[rs]+max(lk[ls]-rk[rs],0);//上传}int main(){ freopen("elf.in","r",stdin); freopen("elf.out","w",stdout); read(n); read(m); scanf("%s",c+1); l[1]=1;r[1]=n; build(1,1,n); for (int i=1;i<=m;i++){ scanf("%s",check+1); if (check[1]=='Q'){ read(x); read(y); query(1,x,y); writel(ans1);writeln(ans2); ans1=0;ans2=0; } else { read(x); change(1,x); } }}