Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 1858 [Scoi2010]序列操作

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都需要给出回答,聪明的程序员们,你们能帮助他吗?

线段树代码题

维护最左边,最右边区间内最长连续0,1的个数

异或的时候交换一下0,1的信息就好

感觉就是如果你不能快速统计出一个元素的信息,你就维护一些可以合并的信息,然后快速合并

比如这个0,1,如果你不维护连续0,那么异或以后你是无法快速统计出异或后的连续1的答案的

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
const int N = 101100;
int a[N],n,m;
int sum[N<<2];
int cov_1[N<<2],cov_2[N<<2];//_1维护把区间全部变成某个数,_2维护把区间取反 
int ln[N<<2],rn[N<<2],mn[N<<2];
int l0[N<<2],r0[N<<2],m0[N<<2];//应对取反操作。。
int max=-1; 
inline int pushup(int cur,int x){
    sum[cur]=sum[cur<<1]+sum[cur<<1|1];

    if(sum[cur<<1]==(x+1>>1)){ln[cur]=sum[cur<<1]+ln[cur<<1|1];l0[cur]=0; }//左叶子全为1
    else{ln[cur]=ln[cur<<1];}

    if(sum[cur<<1|1]==(x>>1)){rn[cur]=sum[cur<<1|1]+rn[cur<<1];r0[cur]=0;}
    else{rn[cur]=rn[cur<<1|1],r0[cur]=r0[cur<<1|1];}

    if(sum[cur<<1]==0){l0[cur]=((x+1)>>1)+l0[cur<<1|1];ln[cur]=0;}
    else{l0[cur]=l0[cur<<1];}
    if(sum[cur<<1|1]==0){r0[cur]=(x>>1)+r0[cur<<1];rn[cur]=0;}
    else{r0[cur]=r0[cur<<1|1];}

    mn[cur]=std::max(mn[cur<<1],std::max(mn[cur<<1|1],rn[cur<<1]+ln[cur<<1|1]));
    m0[cur]=std::max(m0[cur<<1],std::max(m0[cur<<1|1],r0[cur<<1]+l0[cur<<1|1]));
}
//对一个操作先修改再取反 
inline int pushdown(int cur,int x){
    if(cov_1[cur]!=-1){
        cov_1[cur<<1]=cov_1[cur];
        cov_1[cur<<1|1]=cov_1[cur];
        cov_2[cur<<1]=0;
        cov_2[cur<<1|1]=0;
        sum[cur<<1]=(x+1>>1)*cov_1[cur];
        sum[cur<<1|1]=(x>>1)*cov_1[cur];
        ln[cur<<1]=rn[cur<<1]=mn[cur<<1]=(x+1>>1)*cov_1[cur];
        l0[cur<<1]=r0[cur<<1]=m0[cur<<1]=(x+1>>1)-ln[cur<<1];
        ln[cur<<1|1]=rn[cur<<1|1]=mn[cur<<1|1]=(x>>1)*cov_1[cur]; 
        l0[cur<<1|1]=r0[cur<<1|1]=m0[cur<<1|1]=(x>>1)-rn[cur<<1|1]; 
        cov_1[cur]=-1;
    }
    if(cov_2[cur]){
        if(cov_2[cur<<1]==-1) cov_2[cur<<1]=1;
        if(cov_2[cur<<1|1]==-1) cov_2[cur<<1|1]=1;
        cov_2[cur<<1]^=1;
        cov_2[cur<<1|1]^=1;
        sum[cur<<1]=(x+1>>1)-sum[cur<<1];
        sum[cur<<1|1]=(x>>1)-sum[cur<<1|1];
        std::swap(ln[cur<<1],l0[cur<<1]);std::swap(ln[cur<<1|1],l0[cur<<1|1]);
        std::swap(rn[cur<<1],r0[cur<<1]);std::swap(rn[cur<<1|1],r0[cur<<1|1]);
        std::swap(mn[cur<<1],m0[cur<<1]);std::swap(mn[cur<<1|1],m0[cur<<1|1]);
        cov_2[cur]=0;
    }
}
void cancel(int l,int r,int cur){
    if(r==l) return ;
    cov_2[cur]=0;
    int mid=l+r>>1;
    cancel(l,mid,cur<<1);
    cancel(mid+1,r,cur<<1|1);
}
inline int change(int l,int r,int L,int R,int cur,int od){
    if(L<=l&&r<=R){
        if(od!=2){
            sum[cur]=(r-l+1)*od;
            ln[cur]=rn[cur]=mn[cur]=od*(r-l+1);
            l0[cur]=r0[cur]=m0[cur]=r-l+1-ln[cur]; 
            cov_1[cur]=od;
            cov_2[cur]=0;
            //cancel(l,r,cur);
        }
        if(od==2){
            sum[cur]=r-l+1-sum[cur];
            std::swap(ln[cur],l0[cur]);
            std::swap(rn[cur],r0[cur]);
            std::swap(mn[cur],m0[cur]);
            cov_2[cur]^=1;
        }
        return 0;
    }
    pushdown(cur,r-l+1);
    int mid = l+r>>1;
    if(L<=mid) change(l,mid,L,R,cur<<1,od);
    if(R>mid) change(mid+1,r,L,R,cur<<1|1,od);
    pushup(cur,r-l+1);
    return 0;
}
inline int ask(int l,int r,int L,int R,int cur,int od){
    if(L<=l&&r<=R){
        if(od==3){
            return sum[cur];
        }
        if(od==4){
            max=std::max(max,mn[cur]);
            return mn[cur];
        }
        return 0;
    }
    pushdown(cur,r-l+1);
    int mid = l+r>>1,ans=0;
    if(od==4){
        max=std::max(std::min(mid-L+1,rn[cur<<1])+std::min(R-mid,ln[cur<<1|1]),max);
    }
    if(L<=mid) ans+=ask(l,mid,L,R,cur<<1,od);
    if(R>mid) ans+=ask(mid+1,r,L,R,cur<<1|1,od);
    return ans;
}
inline int build(int l,int r,int cur){
    if(l==r){
        sum[cur]=a[l];
        mn[cur]=ln[cur]=rn[cur]=a[l];
        l0[cur]=r0[cur]=m0[cur]=1-a[l];
        return 0;
    }
    int mid = l+r>>1;
    build(l,mid,cur<<1);
    build(mid+1,r,cur<<1|1);
    pushup(cur,r-l+1);
    return 0 ; 
}
int main (){
//    freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
    memset(cov_1,-1,sizeof(cov_1));
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    while(m--){
        int od,l,r;
        scanf("%d %d %d",&od,&l,&r);
        l++,r++;
        if(l>r) std::swap(l,r);
        if(od>=0&&od<=2){
            change(1,n,l,r,1,od);
        }
        else{
            max=-1;
            int ans = ask(1,n,l,r,1,od);
            if(od==4)ans=max;
            printf("%d\n",ans); 
        }//     for(int i=1;i<=n;++i)
           //           printf("%d",ask(1,n,i,i,1,3)); printf("\n");
    }
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/225
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      线段树      BZOJ 1858 [Scoi2010]序列操作
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

BZOJ 1858 [Scoi2010]序列操作
lxhgww最近收到了一个01序列,序列里面包含了n个数,这些数要么是0,要么是1,现在对于这个序列有五种变换操作和询问操作: 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, …
扫描二维码继续阅读
2018-12-19