BZOJ-1858: [Scoi2010]序列操作

[文章目录]

Description

lxhgww最近收到了一个01序列,序列里面包含了n个数,这些数要么是0,要么是1,现在对于这个序列有五种变换操作和询问操作: 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作,lxhgww都需要给出回答,聪明的程序员们,你们能帮助他吗?

啊,幸福来得太突然,还没有大的输出调试就把肉眼编译过的交上去了,A啦哈哈哈哈哈哈哈哈。

额,属于看着都会,写不对,贼难调那类的大恶心线段树。

打的时候注意一下三个lazy的关系,没错,三个。然后维护的参数是。。8个,嗯,就这样:)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ls pos<<1
#define rs pos<<1|1
#define N 101000
using namespace std;
int n,m,w[N];
struct seg
{
    int sum1[N<<2],sum0[N<<2],mx1[N<<2],mx0[N<<2];
    int mx1l[N<<2],mx0l[N<<2],mx1r[N<<2],mx0r[N<<2];
    bool lz1[N<<2],lz0[N<<2],lzyh[N<<2];
    void pushup(int pos)
    {
        sum1[pos]=sum1[ls]+sum1[rs];
        sum0[pos]=sum0[ls]+sum0[rs];
        mx1[pos]=max(max(mx1[ls],mx1[rs]),mx1r[ls]+mx1l[rs]);
        mx0[pos]=max(max(mx0[ls],mx0[rs]),mx0r[ls]+mx0l[rs]);
        mx0l[pos]= sum1[ls]==0 ? sum0[ls]+mx0l[rs] : mx0l[ls];
        mx1l[pos]= sum0[ls]==0 ? sum1[ls]+mx1l[rs] : mx1l[ls];
        mx0r[pos]= sum1[rs]==0 ? sum0[rs]+mx0r[ls] : mx0r[rs];
        mx1r[pos]= sum0[rs]==0 ? sum1[rs]+mx1r[ls] : mx1r[rs];
    }
    void pushdown(int pos)
    {
        if(lz1[pos])
        {
            lz0[ls]=lzyh[ls]=0; lz1[ls]=1;
            sum1[ls]+=sum0[ls]; sum0[ls]=0;
            mx1l[ls]=mx1r[ls]=mx1[ls]=sum1[ls];
            mx0l[ls]=mx0r[ls]=mx0[ls]=0;
            lz0[rs]=lzyh[rs]=0; lz1[rs]=1;
            sum1[rs]+=sum0[rs]; sum0[rs]=0;
            mx1l[rs]=mx1r[rs]=mx1[rs]=sum1[rs];
            mx0l[rs]=mx0r[rs]=mx0[rs]=0;
            lz1[pos]=0;
        }
        if(lz0[pos])
        {
            lz1[ls]=lzyh[ls]=0; lz0[ls]=1;
            sum0[ls]+=sum1[ls]; sum1[ls]=0;
            mx0l[ls]=mx0r[ls]=mx0[ls]=sum0[ls];
            mx1l[ls]=mx1r[ls]=mx1[ls]=0;
            lz1[rs]=lzyh[rs]=0; lz0[rs]=1;
            sum0[rs]+=sum1[rs]; sum1[rs]=0;
            mx0l[rs]=mx0r[rs]=mx0[rs]=sum0[rs];
            mx1l[rs]=mx1r[rs]=mx1[rs]=0;
            lz0[pos]=0;
        }
        if(lzyh[pos])
        {
            swap(lz0[ls],lz1[ls]);swap(sum0[ls],sum1[ls]);
            swap(mx1l[ls],mx0l[ls]);swap(mx1r[ls],mx0r[ls]);
            swap(mx1[ls],mx0[ls]);if(!lz0[ls]&&!lz1[ls]) lzyh[ls]^=1;
            swap(lz0[rs],lz1[rs]);swap(sum0[rs],sum1[rs]);
            swap(mx1l[rs],mx0l[rs]);swap(mx1r[rs],mx0r[rs]);
            swap(mx1[rs],mx0[rs]);if(!lz0[rs]&&!lz1[rs]) lzyh[rs]^=1;
            lzyh[pos]=0;
        }
    }
    void build(int pos,int l,int r)
    {
        if(l==r)
        {
            if(w[l]) sum1[pos]=mx1[pos]=mx1l[pos]=mx1r[pos]=1;
            else sum0[pos]=mx0[pos]=mx0l[pos]=mx0r[pos]=1;
            return ;
        }
        int mid=l+r>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(pos);
    }
    void fix0(int pos,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r)
        {
            lz1[pos]=lzyh[pos]=0; lz0[pos]=1;
            sum0[pos]+=sum1[pos]; sum1[pos]=0;
            mx0l[pos]=mx0r[pos]=mx0[pos]=sum0[pos];
            mx1l[pos]=mx1r[pos]=mx1[pos]=0;
            return ;
        }
        pushdown(pos);
        int mid=l+r>>1;
        if(y<=mid) fix0(ls,l,mid,x,y);
        else if(x>mid) fix0(rs,mid+1,r,x,y);
        else fix0(ls,l,mid,x,y),fix0(rs,mid+1,r,x,y);
        pushup(pos);
    }
    void fix1(int pos,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r)
        {
            lz0[pos]=lzyh[pos]=0; lz1[pos]=1;
            sum1[pos]+=sum0[pos]; sum0[pos]=0;
            mx1l[pos]=mx1r[pos]=mx1[pos]=sum1[pos];
            mx0l[pos]=mx0r[pos]=mx0[pos]=0;
            return ;
        }
        pushdown(pos);
        int mid=l+r>>1;
        if(y<=mid) fix1(ls,l,mid,x,y);
        else if(x>mid) fix1(rs,mid+1,r,x,y);
        else fix1(ls,l,mid,x,y),fix1(rs,mid+1,r,x,y);
        pushup(pos);
    }
    void fixyh(int pos,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r)
        {
            swap(lz0[pos],lz1[pos]);swap(sum0[pos],sum1[pos]);
            swap(mx1l[pos],mx0l[pos]);swap(mx1r[pos],mx0r[pos]);
            swap(mx1[pos],mx0[pos]);if(!lz0[pos]&&!lz1[pos]) lzyh[pos]^=1;
            return ;
        }
        pushdown(pos);
        int mid=l+r>>1;
        if(y<=mid) fixyh(ls,l,mid,x,y);
        else if(x>mid) fixyh(rs,mid+1,r,x,y);
        else fixyh(ls,l,mid,x,y),fixyh(rs,mid+1,r,x,y);
        pushup(pos);
    }
    int query_sum(int pos,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r) {return sum1[pos];}
        int mid=l+r>>1;
        pushdown(pos);
        if(y<=mid) return query_sum(ls,l,mid,x,y);
        else if(x>mid) return query_sum(rs,mid+1,r,x,y);
        else return query_sum(ls,l,mid,x,y)+query_sum(rs,mid+1,r,x,y);
    }
    int getleft(int pos,int l,int r,int y)
    {
        if(y>=r) return mx1l[pos];
        pushdown(pos);
        int mid=l+r>>1;
        if(y<=mid) return getleft(ls,l,mid,y);
        else if(sum0[ls]==0) return sum1[ls]+getleft(rs,mid+1,r,y);
        else return getleft(ls,l,mid,y);
    }
    int getright(int pos,int l,int r,int y)
    {
        if(y<=l) return mx1r[pos];
        pushdown(pos);
        int mid=l+r>>1;
        if(y>mid) return getright(rs,mid+1,r,y);
        else if(sum0[rs]==0) return sum1[rs]+getright(ls,l,mid,y);
        else return getright(rs,mid+1,r,y);
    }
    int query_mx(int pos,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r) {return mx1[pos];}
        int mid=l+r>>1;
        pushdown(pos);
        if(y<=mid) return query_mx(ls,l,mid,x,y);
        else if(x>mid) return query_mx(rs,mid+1,r,x,y);
        else return max(max(query_mx(ls,l,mid,x,y),query_mx(rs,mid+1,r,x,y)),getright(ls,l,mid,x)+getleft(rs,mid+1,r,y));
    }
}T;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    T.build(1,1,n);
    int sw,ll,rr;
    while(m--)
    {
        scanf("%d%d%d",&sw,&ll,&rr);ll++,rr++;
        switch(sw)
        {
            case 0:T.fix0(1,1,n,ll,rr);break;
            case 1:T.fix1(1,1,n,ll,rr);break;
            case 2:T.fixyh(1,1,n,ll,rr);break;
            case 3:printf("%d\n",T.query_sum(1,1,n,ll,rr));break;
            case 4:printf("%d\n",T.query_mx(1,1,n,ll,rr));break;
        }
    }
    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注