【BZOJ-1858】序列操作线段树

1858: [Scoi2010]序列操作

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1961 Solved: 991
[Submit][Status][Discuss]

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

Input

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目第二行包括n个数，表示序列的初始状态接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作="" <="" div="">

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

HINT

对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000

Source

Day2

Solution

线段树裸题，但是...

维护各种量:左/右端点,区间大小,覆盖标记,翻转标记,1/0的数量,连续出现次数,左右段的量,是否完全覆盖....

标记之间各种相互作用...比如覆盖标记时清零翻转标记...

向上更新值的时候,不太同于以往..分类讨论左右段来合并..

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100010
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f; 
}
int n,m;
struct Treenode{int tag,rev,l,r,size,sum[2],L[2],R[2],num[2],da;}tree[maxn<<2];
inline Treenode merge(Treenode a,Treenode b)
{
    Treenode re;
    re.l=a.l; re.r=b.r; re.size=re.r-re.l+1; re.rev=0; re.tag=-1;
    re.L[0]=a.L[0]; re.L[1]=a.L[1]; re.R[0]=b.R[0]; re.R[1]=b.R[1];
    re.num[0]=max(a.num[0],b.num[0]); re.num[1]=max(a.num[1],b.num[1]);
    re.num[0]=max(re.num[0],a.R[0]+b.L[0]); re.num[1]=max(re.num[1],a.R[1]+b.L[1]);
    re.sum[0]=a.sum[0]+b.sum[0]; re.sum[1]=a.sum[1]+b.sum[1];
    if(a.da==0) re.L[0]=a.num[0]+b.L[0]; else if(a.da==1) re.L[1]=a.num[1]+b.L[1];
    if(b.da==0) re.R[0]=b.num[0]+a.R[0]; else if(b.da==1) re.R[1]=b.num[1]+a.R[1];
    if(a.da==b.da) re.da=a.da; else re.da=-1;
    return re;
}
inline void update(int now)
{
    tree[now]=merge(tree[now<<1],tree[now<<1|1]);
}
inline void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    tree[k].tag=-1; tree[k].size=r-l+1;
    if(l==r)
    {
        scanf("%d",&tree[k].da);
        if(tree[k].da)
        {tree[k].L[1]=tree[k].R[1]=tree[k].num[1]=tree[k].sum[1]=1;}
        else
        {tree[k].L[0]=tree[k].R[0]=tree[k].num[0]=tree[k].sum[0]=1;}
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    update(k);
}
inline void paintrev(int now)
{
    swap(tree[now].L[0],tree[now].L[1]);
    swap(tree[now].R[0],tree[now].R[1]);
    swap(tree[now].num[0],tree[now].num[1]);
    swap(tree[now].sum[0],tree[now].sum[1]);
    if (tree[now].da!=-1) tree[now].da^=1; 
}
inline void painttag(int now,int D)
{
    tree[now].rev=0;
    if (D!=0)
        {
            tree[now].sum[0]=tree[now].L[0]=tree[now].R[0]=tree[now].num[0]=0,
            tree[now].sum[1]=tree[now].L[1]=tree[now].R[1]=tree[now].num[1]=tree[now].size; 
        }
    else
        {
            tree[now].sum[0]=tree[now].L[0]=tree[now].R[0]=tree[now].num[0]=tree[now].size,
            tree[now].sum[1]=tree[now].L[1]=tree[now].R[1]=tree[now].num[1]=0;
        }
    tree[now].da=D;
}
inline void pushdown(int now)
{
    if (tree[now].l==tree[now].r) return;
    if (tree[now].tag!=-1)
        {
            tree[now<<1].tag=tree[now<<1|1].tag=tree[now].tag;
            painttag(now<<1,tree[now].tag); painttag(now<<1|1,tree[now].tag); tree[now].tag=-1;
        }
    if (tree[now].rev)
        {
            tree[now<<1].rev^=1; tree[now<<1|1].rev^=1;
            paintrev(now<<1); paintrev(now<<1|1); tree[now].rev=0;
        }
}
inline void change(int now,int L,int R,int D)
{
    pushdown(now);
    if(tree[now].l==L && tree[now].r==R) {painttag(now,D);tree[now].tag=D;return;}
    int mid=(tree[now].l+tree[now].r)>>1;
    if(mid>=R) change(now<<1,L,R,D);
        else if(mid<L) change(now<<1|1,L,R,D);
            else change(now<<1,L,mid,D),change(now<<1|1,mid+1,R,D);
    update(now);
}
inline void reserv(int now,int L,int R)
{
    pushdown(now);
    if(tree[now].l==L && tree[now].r==R) {paintrev(now);tree[now].rev^=1;return;}
    int mid=(tree[now].l+tree[now].r)>>1;
    if(mid>=R) reserv(now<<1,L,R);
        else if(mid<L) reserv(now<<1|1,L,R);
            else reserv(now<<1,L,mid),reserv(now<<1|1,mid+1,R);
    update(now);
}
inline int asksum(int now,int L,int R)
{
    pushdown(now);
    if(tree[now].l==L && tree[now].r==R) return tree[now].sum[1];
    int mid=(tree[now].l+tree[now].r)>>1;
    if(mid>=R) return asksum(now<<1,L,R);
        else if(mid<L) return asksum(now<<1|1,L,R);
            else return asksum(now<<1,L,mid)+asksum(now<<1|1,mid+1,R);
    update(now);
}
inline Treenode asknum(int now,int L,int R)
{
    pushdown(now);
    if (L==tree[now].l && R==tree[now].r) return tree[now];
    int mid=(tree[now].l+tree[now].r)>>1;
    if (mid>=R) return asknum(now<<1,L,R);
    else if(mid<L)return asknum(now<<1|1,L,R);
    else return merge(asknum(now<<1,L,mid),asknum(now<<1|1,mid+1,R));
}
int main()
{
    n=read(),m=read();build(1,1,n);
    while (m--)
        {
            int opt=read(),l=read(),r=read(); l++;r++;
            switch (opt)
                {
                    case 0: change(1,l,r,0);break;
                    case 1: change(1,l,r,1);break;
                    case 2: reserv(1,l,r);break;
                    case 3: printf("%d
",asksum(1,l,r));break;
                    case 4: printf("%d
",asknum(1,l,r).num[1]);break;
                }
        }
    return 0;
}

手一点误就调好久,巨恶心.. 自己讨论的不够好..还重敲了一遍....至于压代码?Char哥比我短80行..