题目：
http://www.bnuoj.com/bnuoj/problem_show.php?pid=53081
思路：
将‘（’看作1，‘）’看作-1，每次询问：从x开始所有前缀的前缀和均非负，且和为0的最长前缀。
维护线段树节点代表区间的最小前缀和，每次询问处理方式为：
若当前区间[x，i]合并当前节点后最小前缀和非负，则合并，否则不合并且终止查询。
输出合并后的区间内最小前缀对应的长度即可。
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
struct line
{
int len,mi,id,sum;
line operator+(const line &l)const
{
line tmp=*this;
tmp.len+=l.len;
if (sum+l.mi<=tmp.mi)
tmp.mi=sum+l.mi,tmp.id=l.id;
tmp.sum+=l.sum;
return tmp;
}
}a[N*4];
char s[N];
void build(int i,int l,int r)
{
if (l==r)
{
if (s[l]=='(') a[i]={1,1,l,1};
else a[i]={1,-1,l,-1};
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
a[i]=a[i*2]+a[i*2+1];
}
void cg(int i,int l,int r,int x)
{
if (l==r)
{
if (s[l]=='(') a[i]={1,1,l,1};
else a[i]={1,-1,l,-1};
return;
}
int mid=(l+r)/2;
if (x<=mid) cg(i*2,l,mid,x);
else cg(i*2+1,mid+1,r,x);
a[i]=a[i*2]+a[i*2+1];
}
line L;
bool get(int i,int l,int r,int x)
{
if (x<=l)
{
if ((L+a[i]).mi>=0)
{
L=L+a[i];
return 1;
}
else
{
if (l==r) return 0;
int mid=(l+r)/2;
if (get(i*2,l,mid,x))
get(i*2+1,mid+1,r,x);
return 0;
}
}
int mid=(l+r)/2;
if (x<=mid)
{
if (get(i*2,l,mid,x)&&get(i*2+1,mid+1,r,x)) return 1;
return 0;
}
if (get(i*2+1,mid+1,r,x)) return 1;
return 0;
}
int main()
{
int t; scanf("%d",&t);
while(t--)
{
int n,q; scanf("%d%d",&n,&q);
scanf("%s",s+1);
build(1,1,n);
while(q--)
{
int tp,x; scanf("%d%d",&tp,&x);
if (tp==1)
{
s[x]='('+')'-s[x];
cg(1,1,n,x);
}
else
{
L={0,0,x-1,0};
get(1,1,n,x);
printf("%d\n",L.id-x+1);
}
}
}
}
