BNUOJ 53081 线段树区间合并

题目：

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);
            }
        }
    }
}