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

2021-09-06 10:11:42

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=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int n,m;

struct Treenode{int tag,rev,l,r,size,sum[],L[],R[],num[],da;}tree[maxn<<];

inline Treenode merge(Treenode a,Treenode b)

{

    Treenode re;

    re.l=a.l; re.r=b.r; re.size=re.r-re.l+; re.rev=; re.tag=-;

    re.L[]=a.L[]; re.L[]=a.L[]; re.R[]=b.R[]; re.R[]=b.R[];

    re.num[]=max(a.num[],b.num[]); re.num[]=max(a.num[],b.num[]);

    re.num[]=max(re.num[],a.R[]+b.L[]); re.num[]=max(re.num[],a.R[]+b.L[]);

    re.sum[]=a.sum[]+b.sum[]; re.sum[]=a.sum[]+b.sum[];

    if(a.da==) re.L[]=a.num[]+b.L[]; else if(a.da==) re.L[]=a.num[]+b.L[];

    if(b.da==) re.R[]=b.num[]+a.R[]; else if(b.da==) re.R[]=b.num[]+a.R[];

    if(a.da==b.da) re.da=a.da; else re.da=-;

    return re;

}

inline void update(int now)

{

    tree[now]=merge(tree[now<<],tree[now<<|]);

}

inline void build(int k,int l,int r)

{

    tree[k].l=l;tree[k].r=r;

    tree[k].tag=-; tree[k].size=r-l+;

    if(l==r)

    {

        scanf("%d",&tree[k].da);

        if(tree[k].da)

        {tree[k].L[]=tree[k].R[]=tree[k].num[]=tree[k].sum[]=;}

        else

        {tree[k].L[]=tree[k].R[]=tree[k].num[]=tree[k].sum[]=;}

        return;

    }

    int mid=(l+r)>>;

    build(k<<,l,mid);build(k<<|,mid+,r);

    update(k);

}

inline void paintrev(int now)

{

    swap(tree[now].L[],tree[now].L[]);

    swap(tree[now].R[],tree[now].R[]);

    swap(tree[now].num[],tree[now].num[]);

    swap(tree[now].sum[],tree[now].sum[]);

    if (tree[now].da!=-) tree[now].da^=;

}

inline void painttag(int now,int D)

{

    tree[now].rev=;

    if (D!=)

        {

            tree[now].sum[]=tree[now].L[]=tree[now].R[]=tree[now].num[]=,

            tree[now].sum[]=tree[now].L[]=tree[now].R[]=tree[now].num[]=tree[now].size;

        }

    else

        {

            tree[now].sum[]=tree[now].L[]=tree[now].R[]=tree[now].num[]=tree[now].size,

            tree[now].sum[]=tree[now].L[]=tree[now].R[]=tree[now].num[]=;

        }

    tree[now].da=D;

}

inline void pushdown(int now)

{

    if (tree[now].l==tree[now].r) return;

    if (tree[now].tag!=-)

        {

            tree[now<<].tag=tree[now<<|].tag=tree[now].tag;

            painttag(now<<,tree[now].tag); painttag(now<<|,tree[now].tag); tree[now].tag=-;

        }

    if (tree[now].rev)

        {

            tree[now<<].rev^=; tree[now<<|].rev^=;

            paintrev(now<<); paintrev(now<<|); tree[now].rev=;

        }

}

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

    if(mid>=R) change(now<<,L,R,D);

        else if(mid<L) change(now<<|,L,R,D);

            else change(now<<,L,mid,D),change(now<<|,mid+,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^=;return;}

    int mid=(tree[now].l+tree[now].r)>>;

    if(mid>=R) reserv(now<<,L,R);

        else if(mid<L) reserv(now<<|,L,R);

            else reserv(now<<,L,mid),reserv(now<<|,mid+,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[];

    int mid=(tree[now].l+tree[now].r)>>;

    if(mid>=R) return asksum(now<<,L,R);

        else if(mid<L) return asksum(now<<|,L,R);

            else return asksum(now<<,L,mid)+asksum(now<<|,mid+,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)>>;

    if (mid>=R) return asknum(now<<,L,R);

    else if(mid<L)return asknum(now<<|,L,R);

    else return merge(asknum(now<<,L,mid),asknum(now<<|,mid+,R));

}

int main()

{

    n=read(),m=read();build(,,n);

    while (m--)

        {

            int opt=read(),l=read(),r=read(); l++;r++;

            switch (opt)

                {

                    case : change(,l,r,);break;

                    case : change(,l,r,);break;

                    case : reserv(,l,r);break;

                    case : printf("%d\n",asksum(,l,r));break;

                    case : printf("%d\n",asknum(,l,r).num[]);break;

                }

        }

    return ;

}

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

码农公寓