对自己 & \(RNG\) ：骄兵必败

\(lpl\)加油！

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

错误日志：内容较多且重要，将写在下方加粗

Solution

线段树，需要维护以下信息：

\(sum\) 区间 \(1\) 的个数
\(max[0/1]\) 区间内 \(0/1\) 最长连续子段
\(lmax[0/1]\) 包含区间左端点最长 \(0/1\) 子段
\(rmax[0/1]\) 包含区间右端点最长 \(0/1\) 子段

鉴于有区间操作，这里还需要两个标记：

5. \(lazy = {-1, 0, 1}\) 为 \(-1\) 表示无状态，为 \(0/1\) 表示区间全部赋值为 \(0/1\)

6. \(rev = {0, 1}\) 区间是否翻转

需要维护的元素较多，先讲 \(pushup\)

区间和直接相加即可

包含左端点的连续子段有两种情况：

直接继承左区间的 \(lmax\)
当左区间全满 / 全空时，左端点可以跨越，加上右区间的部分

右区间更新同理

对于区间最长连续子段，有以下三种情况

直接继承左区间的较大值
直接继承右区间的较大值
左区间的含右端点最长子段 + 右区间含左端点最长子段，即最长部分跨越区间分割线

以上需要分 \(0/1\) 讨论，程序中直接两层循环搞定

然后到了难点 \(pushdown\)

我一个需要冲省队的选手竟然直到现在才注意到这点很惨啊

在线段树 \(pushdown\) 操作中，我们需要明确两件事：

标记的优先级

2. 下放某一标记是否会对子节点的其他类型标记有所影响

这里重点讨论第二点（第一点区间全体赋值优先级肯定高于翻转，所以优先拆区间赋值标记，拆标记时需要将翻转标记清空）

在拆解一个标记时，我们不仅需要明确将此标记下放到子节点， 同类型的标记应该如何改变，而更应明确拆解此标记会对 不同类型的标记有何种影响

明确同类型的影响是一般不会出问题的，如将区间加标记下放时，子节点的区间加标记累加上这个值

以本题为例：

将区间赋值标记拆解时，不仅需要将子区间赋值标记更新为此值，还需要将子节点翻转标记清空（不过这个貌似影响不大，拆赋值标记时会将翻转标记清空的）

将区间翻转标记拆解时，需要分两种情况考虑此标记下推对子区间赋值标记和翻转标记造成的影响

考虑到赋值标记的优先级大于翻转标记， 在有赋值标记的情况下，直接翻转赋值标记

其余情况翻转标记异或等于1

其余见代码虽然很长但用心弄懂会对线段树有一个很深刻的理解

这样完备地考虑所有情况是一个 \(OI\) 选手的基本素养

嗯就这样， \(RNG\) 别丧气，你们是最棒的； \(S8\) ，\(lpl\) 加油！

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 200019;

int num, na;

int v[maxn];

#define lid (id << 1)

#define rid (id << 1) | 1

//int max(int a, int b){return a > b ? a : b;}//听说手写快？

struct seg_tree{

    int l, r;

    int sum;

    int lazy;//-1.NULL  0.全为0  1.全为1

	int rev;

    int max[2], lmax[2], rmax[2];

    }tree[maxn << 2];

void pushup(int id){

    tree[id].sum = tree[lid].sum + tree[rid].sum;

    REP(i, 0, 1){

        tree[id].lmax[i] = tree[lid].lmax[i];

        if(i == 1 && tree[lid].sum == tree[lid].r - tree[lid].l + 1)//左区间全满

            tree[id].lmax[i] += tree[rid].lmax[i];//可以跨越

        else if(i == 0 && tree[lid].sum == 0)//左区间全空

            tree[id].lmax[i] += tree[rid].lmax[i];

        tree[id].rmax[i] = tree[rid].rmax[i];

        if(i == 1 && tree[rid].sum == tree[rid].r - tree[rid].l + 1)

            tree[id].rmax[i] += tree[lid].rmax[i];

        else if(i == 0 && tree[rid].sum == 0)

            tree[id].rmax[i] += tree[lid].rmax[i];

        tree[id].max[i] = tree[lid].rmax[i] + tree[rid].lmax[i];//中间

        tree[id].max[i] = max(tree[id].max[i], tree[lid].max[i]);//继承子区间

        tree[id].max[i] = max(tree[id].max[i], tree[rid].max[i]);

        }

    }

void build(int id, int l, int r){

    tree[id].l = l, tree[id].r = r, tree[id].lazy = -1;

    if(l == r){

        tree[id].sum = v[l];

        tree[id].max[0] = tree[id].lmax[0] = tree[id].rmax[0] = v[l] == 0;

        tree[id].max[1] = tree[id].lmax[1] = tree[id].rmax[1] = v[l] == 1;

        return ;

        }

    int mid = (l + r) >> 1;

    build(lid, l, mid), build(rid, mid + 1, r);

    pushup(id);

    }

void pushdown(int id){

    if(tree[id].lazy != -1){//优先级最高

		tree[id].rev = 0;//清空标记

        int val = tree[id].lazy;

        tree[lid].sum = (tree[lid].r - tree[lid].l + 1) * val;

        tree[rid].sum = (tree[rid].r - tree[rid].l + 1) * val;

        tree[lid].lazy = tree[rid].lazy = val;

		tree[lid].rev = tree[rid].rev = 0;

        tree[lid].max[val]

        = tree[lid].lmax[val]

        = tree[lid].rmax[val]

        = tree[lid].r - tree[lid].l + 1;

        tree[lid].max[val ^ 1]

        = tree[lid].lmax[val ^ 1]

        = tree[lid].rmax[val ^ 1]

        = 0;

        tree[rid].max[val]

        = tree[rid].lmax[val]

        = tree[rid].rmax[val]

        = tree[rid].r - tree[rid].l + 1;

        tree[rid].max[val ^ 1]

        = tree[rid].lmax[val ^ 1]

        = tree[rid].rmax[val ^ 1]

        = 0;

		tree[id].lazy = -1;

        }

    if(tree[id].rev){

        tree[lid].sum = (tree[lid].r - tree[lid].l + 1) - tree[lid].sum;

        tree[rid].sum = (tree[rid].r - tree[rid].l + 1) - tree[rid].sum;

        if(tree[lid].lazy != -1)tree[lid].lazy ^= 1;//综合考虑优先级， 对其他标记的影响

		else tree[lid].rev ^= 1;

		if(tree[rid].lazy != -1)tree[rid].lazy ^= 1;

		else tree[rid].rev ^= 1;

        swap(tree[lid].max[0], tree[lid].max[1]);

        swap(tree[lid].lmax[0], tree[lid].lmax[1]);

        swap(tree[lid].rmax[0], tree[lid].rmax[1]);

        swap(tree[rid].max[0], tree[rid].max[1]);

        swap(tree[rid].lmax[0], tree[rid].lmax[1]);

        swap(tree[rid].rmax[0], tree[rid].rmax[1]);

		tree[id].rev = 0;

        }

    }

void update(int id, int val, int l, int r){

    pushdown(id);

    if(tree[id].l == l && tree[id].r == r){

        if(val == 0 || val == 1){

            tree[id].sum = (tree[id].r - tree[id].l + 1) * val;

            tree[id].lazy = val;

            tree[id].max[val]

            = tree[id].lmax[val]

            = tree[id].rmax[val]

            = tree[id].r - tree[id].l + 1;

            tree[id].max[val ^ 1]

            = tree[id].lmax[val ^ 1]

            = tree[id].rmax[val ^ 1]

            = 0;

            }

        else if(val == 2){

            tree[id].sum = (tree[id].r - tree[id].l + 1) - tree[id].sum;

            tree[id].rev ^= 1;

            swap(tree[id].max[0], tree[id].max[1]);

            swap(tree[id].lmax[0], tree[id].lmax[1]);

            swap(tree[id].rmax[0], tree[id].rmax[1]);

            }

        return ;

        }

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

    if(mid < l)update(rid, val, l, r);

    else if(mid >= r)update(lid, val, l, r);

    else update(lid, val, l, mid), update(rid, val, mid + 1, r);

    pushup(id);

    }

int query(int id, int l, int r){

    pushdown(id);

    if(tree[id].l == l && tree[id].r == r)return tree[id].sum;

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

    if(mid < l)return query(rid, l, r);

    else if(mid >= r)return query(lid, l, r);

    else return query(lid, l, mid) + query(rid, mid + 1, r);

    }

seg_tree Q_max(int id, int l, int r){

    pushdown(id);

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

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

    if(mid < l)return Q_max(rid, l, r);

    else if(mid >= r)return Q_max(lid, l, r);

    else{

        seg_tree ret, L = Q_max(lid, l, mid), R = Q_max(rid, mid + 1, r);

        ret.sum = L.sum + R.sum;

        REP(i, 0, 1){

            ret.lmax[i] = L.lmax[i];

            if(i == 1 && L.sum == L.r - L.l + 1)//左区间全满

                ret.lmax[i] += R.lmax[i];//可以跨越

            else if(i == 0 && L.sum == 0)//左区间全空

                ret.lmax[i] += R.lmax[i];

            ret.rmax[i] = R.rmax[i];

            if(i == 1 && R.sum == R.r - R.l + 1)

                ret.rmax[i] += L.rmax[i];

            else if(i == 0 && R.sum == 0)

                ret.rmax[i] += L.rmax[i];

            ret.max[i] = L.rmax[i] + R.lmax[i];//中间

            ret.max[i] = max(ret.max[i], L.max[i]);//继承子区间

            ret.max[i] = max(ret.max[i], R.max[i]);

            }

        return ret;

        }

    }

int main(){

    num = RD(), na = RD();

    REP(i, 1, num)v[i] = RD();

    build(1, 1, num);

    while(na--){

        int cmd = RD(), l = RD(), r = RD();l++, r++;

        if(cmd == 0)update(1, 0, l, r);

        else if(cmd == 1)update(1, 1, l, r);

        else if(cmd == 2)update(1, 2, l, r);

        else if(cmd == 3)printf("%d\n", query(1, l, r));

        else printf("%d\n", Q_max(1, l, r).max[1]);

        }

    return 0;

    }

巴特西

P2572 [SCOI2010]序列操作

P2572 [SCOI2010]序列操作

Solution

Code

最新文章

热门文章