洛谷 2572 bzoj 1858 [SCOI2010]序列操作 题解

题意简述

你有一个长度为$n$的01序列，支持$m$个操作，操作分五种，形式分别是：

• 0 l r 从$l$到$r$都变成$0$
• 1 l r 从$l$到$r$都变成$1$
• 2 l r 从$l$到$r$全部取反（$0$变成$1$，$1$变成$0$）
• 3 l r 询问$l$到$r$有多少$1$
• 4 l r 询问$l$到$r$最长的连续的$1$有多长

思路框架

线段树多标记。

具体思路

线段树，分几个方面讲

1. 每个节点存什么信息
2. 如何维护这些信息（Update 函数）
3. lazytag 的优先级，以及如何单节点修改，还有如何 PushDown。

节点信息

我们按操作顺序考虑。首先是区间覆盖的操作，那么我们就要维护一个标记，设为 $cover$ 标记（简记为 $C$）。由于 $C$ 取 $0/1$ 都是有意义的，那么就只好用 $-1$ 表示没有标记了。

然后还有取反操作。那么我们维护一个 $flip$ 标记（简记为 $F$ ），$F=0/1$ 表示区间被取反了$F$ 次。由于取反两次就相当于没有取反，所以 $F$ 只需要设置为 $0/1$ 即珂。

然后询问有多少个 $1$。显然我们需要维护区间有多少个 $1$ ，设为 $s[1]$ （$s$ 就是 $sum$ 啦）。然后我们发现，取反完之后， $0$ 变成 $1$，$1$ 变成$0$。所以$1$有的标记，$0$ 都要有。所以我们还有维护区间有多少 $0$，设为 $s[0]$。

然后询问连续的 $1$ 。这个是套路：我们维护从左边起最大连续的 $0/1$ ，设为 $lc[0/1]$（就是left consecutive的简写 ），还有从右边起最大连续的 $0/1$，设为 $rc[0/1]$。还有最长的连续 $0/1$，记为$x$。（这个名字是瞎jb取的，因为没有名字了）

如何维护

众所周知，update 的时候，lazytag 是不重要的。我们直接将其设置为空标记即珂。

显然，$s[0/1]$ 就直接左子树+右子树即珂。

$lc[0/1]$ 就先设置成左子树的 $lc$。如果发现它占满了整个左子树，那就要跨越到右子树去了。此时再加上右子树的 $lc$ 即珂。
$rc$ 同理。

然后 $x$（最长连续的 $0/1$）的维护也很容易，就是左子树连续的 $1$，右子树连续的 $1$，还有左子树的右连续（$rc$）+右子树的左连续（$lc$），三个取 $max$。

（实现小技巧：我们珂以把节点打个 $struct$，然后封装一个加号）
先放个代码上来，方便理解

复制

struct node{int l,r,f,c,lc[2],rc[2],s[2],x[2];}; 
//l,r表示当前节点表示的区间
//f,c是两个tag
//lc,rc,s,x和上面一样，表示左连续，右连续，总计数，最大连续
node operator+(node ls,node rs)
{
    node ans;
    ans.l=ls.l; ans.r=rs.r; //这个不用我讲吧...
    ans.f=0,ans.c=-1; //标记
    for(int i=0;i<2;++i)
    {
        ans.lc[i]=ls.lc[i]; if (ls.lc[i]==ls.r-ls.l+1) ans.lc[i]+=rs.lc[i];
        //默认直接取左儿子的。如果满了，再加上右儿子的左连续
        ans.rc[i]=rs.rc[i]; if (rs.rc[i]==rs.r-rs.l+1) ans.rc[i]+=ls.rc[i];
        //rc同理
        ans.s[i]=ls.s[i]+rs.s[i];
        //总计数比较方便，直接左右加起来即珂
        ans.x[i]=max(max(ls.x[i],rs.x[i]),ls.rc[i]+rs.lc[i]);
        //最长连续要分三种情况讨论
    }
    return ans;
}

lazytag的优先级&如何维护lazytag

单区间修改

1. 覆盖操作：显然，覆盖的优先级绝对大于取反，所以先令 $F=0$。接着，假设我们都覆盖上了$c$，$c=0/1$。然后 $lc[c],rc[c],s[c],x[c]$ 都等于区间长度，而另一个颜色（$c$ 取反）的$lc,rc,s,x$ 都等于$0$。

2. 如果是取反的操作，因为是低优先级的操作，所以直接修改 $F$ 标记即珂。由于取反完之后，$0$ 变成 $1$，$1$ 变成 $0$，所以我们只需要把 $lc,rc,s,x$的$0/1$ 两维交换一下即珂。

PushDown

PushDown 的时候，先操作 $C$ 标记，再操作 $F$ 标记。我们下传标记的时候，只对儿子作修改，而不对本身作修改（因为在 PushDown 前面一次单区间修改的时候，应该已经改过了）。所以如果遇到“先覆盖后翻转”的情况，就不会错误地把 $F$ 标记删掉了。而两个儿子也是 $C$ 标记先到，$F$ 后到，所以儿子节点的 $F$ 标记也不会被错删掉。

一个小问题：如何写最长连续1的Query函数（代码中的QueryLen）

Query 函数返回一个线段树节点即珂。最后取节点的 $x[1]$ 属性，就是最长连续 $1$ 的长度了。

完整代码（超长）

复制

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    // #define F(i,l,r) for(int i=l;i<=r;++i)
    // 为了不和F标记重名，删掉了这个define
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        for(int i=1;i<=cnt;++i)
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    } //这些都是次要内容
    //以下正片
    //==============================
    struct node{int l,r,f,c,lc[2],rc[2],s[2],x[2];}; 
    //一个线段树节点
    node operator+(node ls,node rs) //这一段上面有
    {
        node ans;
        ans.l=ls.l; ans.r=rs.r;
        ans.f=0,ans.c=-1;
        for(int i=0;i<2;++i)
        {
            ans.lc[i]=ls.lc[i]; if (ls.lc[i]==ls.r-ls.l+1) ans.lc[i]+=rs.lc[i];
            ans.rc[i]=rs.rc[i]; if (rs.rc[i]==rs.r-rs.l+1) ans.rc[i]+=ls.rc[i];
            ans.s[i]=ls.s[i]+rs.s[i];
            ans.x[i]=max(max(ls.x[i],rs.x[i]),ls.rc[i]+rs.lc[i]);
        }
        return ans;
    }
    class SegmentTree
    {
    public:
        node tree[N<<2];

        #define ls index<<1
        #define rs index<<1|1

        #define LC tree[index].lc
        #define RC tree[index].rc
        #define S  tree[index].s
        #define X  tree[index].x
        #define L  tree[index].l
        #define R  tree[index].r
        #define C  tree[index].c
        #define F  tree[index].f

        #define lLC tree[ls].lc
        #define lRC tree[ls].rc
        #define lS  tree[ls].s
        #define lX  tree[ls].x
        #define lL  tree[ls].l
        #define lR  tree[ls].r
        #define lC  tree[ls].c
        #define lF  tree[ls].f

        #define rLC tree[rs].lc
        #define rRC tree[rs].rc
        #define rS  tree[rs].s
        #define rX  tree[rs].x
        #define rL  tree[rs].l
        #define rR  tree[rs].r
        #define rC  tree[rs].c
        #define rF  tree[rs].f //中二define，让代码简介一点
        void Update(int index=1) //这个似乎就很好写了对吧
        {
            tree[index]=tree[ls]+tree[rs];
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;
            if (l==r)
            {
                int x; scanf("%d",&x);
                C=-1;F=0; // 注意: C的空标记为-1
                S[x]=LC[x]=RC[x]=X[x]=1;
                x^=1;
                S[x]=LC[x]=RC[x]=X[x]=0;
                return;
            }
            int mid=(l+r)>>1;
            Build(l,mid,ls); Build(mid+1,r,rs);
            Update(index);
        }
        void FlipOne(int index=1)
        {
            F^=1;
            //注意: F^=1即珂
            swap(LC[0],LC[1]); 
            swap(RC[0],RC[1]); 
            swap(S[0],S[1]); 
            swap(X[0],X[1]);
            //把0和1对应的属性换一下
        } 
        void ChangeOne(int x,int index=1)
        {
            F=0; //清空F标记
            C=x; 
            S[x]=LC[x]=RC[x]=X[x]=R-L+1; //x的属性全部设置为区间长度,x^1的属性全部为0
            x^=1;
            S[x]=LC[x]=RC[x]=X[x]=0;
        }
        //封装单区间修改函数，代码看起来结构清晰些(?)
        void PushDown(int index=1)
        {
            //先传C标记，再传F标记
            if (~C)
            {
                ChangeOne(C,ls); ChangeOne(C,rs);
                C=-1;
            }
            if (F)
            {
                FlipOne(ls); FlipOne(rs);
                F=0;
            }
        }
        void Change(int l,int r,int x,int index=1) //覆盖[l,r]为x
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return ChangeOne(x,index);
            PushDown(index);
            Change(l,r,x,ls); Change(l,r,x,rs);
            Update(index);
        }
        void Flip(int l,int r,int index=1) //区间[l,r]翻转
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return FlipOne(index);
            PushDown(index);
            Flip(l,r,ls); Flip(l,r,rs);
            Update(index);
        }
        int Query1(int l,int r,int index=1) //询问[l,r]中1的数量
        {
            if (l>R or L>r) return 0;
            if (l<=L and R<=r) return S[1];
            PushDown(index);
            return Query1(l,r,ls)+Query1(l,r,rs);
        }
        node QueryLen(int l,int r,int index=1) //询问[l,r]中连续1的长度
        {
            if (l<=L and R<=r) return tree[index]; //返回一个线段树节点
            PushDown(index);
            int mid=(L+R)>>1;
            if (r<=mid) return QueryLen(l,r,ls);
            if (l>mid)  return QueryLen(l,r,rs);
            return QueryLen(l,mid,ls)+QueryLen(mid+1,r,rs); //这样用节点合并就珂以了，是不是很简单呢
        }
    }T;

    int n,m;
    void Input()
    {
        Rd(2,&n,&m);
        T.Build(1,n);
    }

    void Soviet()
    {
        for(int i=1;i<=m;++i)
        {
            int o,l,r;Rd(3,&o,&l,&r);
            ++l,++r; //0编号转1编号
            if (o==0) T.Change(l,r,0);
            if (o==1) T.Change(l,r,1);
            if (o==2) T.Flip(l,r);
            if (o==3) printf("%d\n",T.Query1(l,r));
            if (o==4) printf("%d\n",T.QueryLen(l,r).x[1]); //取x[1]属性就是答案啦
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}