hdu4918 (树分治的维护)
ACM-ICPC 2018 沈阳赛区网络预赛 E. The cake is a lie(最小圆覆盖至少m个点)

BNUOJ 53081 线段树区间合并

zjhl2 posted @ 2018年4月10日 01:10 in with tags 二分 线段树 , 647 阅读

题目:

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);
            }
        }
    }
}
Avatar_small
NCERT Biology Questi 说:
2022年9月28日 19:24

Biology is the study of the life of flora and fauna. Biology talks about organisms and how they react to certain toxins when you mix things up. Biology has a long history which showed impacted people in negative and positive ways. Biology is the study of the life of flora and fauna. NCERT Biology Question Paper Class 9 Biology talks about organisms and how they react to certain toxins when you mix things up. Biology has a long history which showed impacted people in negative and positive ways.Biology is one of the interesting studies with practical experiments which helps the students in understanding better way.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter