做[SCOI2010] 序列操作有感

前言

说实话，虽然线段树的题做了不算少，但是对于多懒标记的这种线段树专题的一些细节并不是很清楚。这种纯数据结构的题大概也不会考

今天再次拿到两种以前没有放一起维护过的懒标记——区间覆盖和区间取反，也查了很多资料，但总感觉还有一些说不清道不明的迷惑，所以打算写点东西记录一下理清思路（本篇文章废话较多，请各位巨佬嘴下留情）

正文

好了，先来看题

题目描述

给定一个长度为$n$的$01$序列，进行$m$次如下形如op l r的五种操作：

• 0 l r，把$a_l,a_{l+1},...,a_{r-1},a_r$全部赋值为$0$

• 1 l r，把$a_l,a_{l+1},...,a_{r-1},a_r$全部赋值为$1$

• 2 l r，把$a_l,a_{l+1},...,a_{r-1},a_r$依次取反

• 3 l r，询问$a_l,a_{l+1},...,a_{r-1},a_r$中$1$的个数

• 4 l r，询问$a_l,a_{l+1},...,a_{r-1},a_r$中连续$1$串的最大长度

对于每个询问，输出对应答案

分析

区间带修查询，还是连续子段长度这种恶心东西，第一时间想到是一道线段树裸题

发现我们要维护的信息还挺多的，先一一列出来（下文统一把op作为操作的编号）

先看询问操作：

操作$3$要求区间中$1$的个数，可以直接用一个计数器维护

操作$4$要求连续$1$串的最大长度，比较麻烦，需要维护最长前缀，最长后缀，最大长度

再看修改操作：

操作$0$和操作$1$只是普通的区间覆盖，维护一个覆盖标记就好

操作$2$是区间取反，这就给我们带来了很多麻烦，意味着我们不仅要维护$1$的信息，对应的还要维护$0$的信息

综上我们需要维护的信息有$10$个：

• $Cnt_0$和$Cnt_1$分别维护$0$和$1$的个数

• $L_{len_0}$和$L_{len_1}$分别维护$0$和$1$的最长前缀

• $R_{len_0}$和$R_{len_1}$分别维护$0$和$1$的最长后缀

• $Max_{len_0}$和$Max_{len_1}$分别维护$0$和$1$的最大连续出现长度

• $Cover$标记维护区间覆盖操作（$-1$表示无赋值，$0$表示赋值成$0$，$1$同理）

• $Reverse$标记维护区间取反操作（$0$表示未取反，$1$表示取反）

过于逆天，看着都头大

好像都很必要，没啥能优化的，但我平常习惯于维护一个$Cnt$，另一个用区间长度$len$来计算，所以就用$len$替换掉$Cnt_0$了

这个时候出现了两个懒标记，一个很重要的事情就是理清它们两个的优先级，但在做这件事情之前，我们先来做另一件事，就是搞清楚操作时懒标记之间的互相影响

很容易能发现，$Cover$实际上是一个很“强”的操作

什么意思呢？

就是说，不管当前区间是个什么离谱状态（不管是加了一个$2,147,483,647$，还是取反了$2^{1e9}-1$次这好像等于取反1次），只要对当前区间进行了覆盖操作，这些离谱标记通通都变成空，只剩我$Cover$一人

所以，进行$Cover$会使$Reverse$标记强制清零

然后考虑$Reverse$对$Cover$标记的影响

如果现在没有$Cover$标记，显然是没有影响的，直接对区间进行正常取反操作就好，然后留下一个$Reverse$标记（取反不会让一个原本就凌乱的区间变成清一色的$0$或$1$）

如果现在已经留有一个$Cover$标记，做一次取反操作相当于将$Cover$取反，但会不会留下一个$Reverse$标记呢？

我们不妨考虑这样一个序列：

$0, 1, 1, 0, 1, 0, 0$

我们先对区间$[2,~4]$进行一次覆盖操作（赋成什么无所谓，就赋成$0$吧），序列变成了这样：

$0, 0, 0, 0, 1, 0, 0$

并在区间$[2,~4]$留下一个$Cover=0$的标记（实际上线段树不是这样划分区间的，但我们现在并不在意这一点）

然后对区间$[1,~4]$进行一次取反操作，序列应当变成：

$1, 1, 1, 1, 1, 0, 0$

并把$[2,~4]$上的$Cover$取反变成$1$，在$[1,1]$上取反并留下$Reverse=1$的取反标记，在$[2,~4]$上要不要留取反标记我们还不确定，姑且就当它没留

但我们都知道，线段树不是这样工作的（至少带懒标记的不是），在这次操作中，对应区间$[3,~4]$的结点不会直接变成$1, 1$，而是等待操作到$[3,~4]$是才进行更新（操作实际上到$[2,~4]$就停下了），所以单独看区间$[3,~4]$仍然是$0, 0$

最后我们对区间$[3,~4]$进行一次查询，此时用到了下传标记：

假设我们先下传覆盖标记，再下传取反标记，当我们把$[2,~4]$上的覆盖标记下传到$[3,~4]$后，$[3,~4]$就真正变成了$1, 1$，这时我们惊喜地发现，我们之前不留取反标记的决策是正确的：如果之前留下了一个取反标记，再下传取反标记是就又把这段区间变成了$0, 0$；而不留下取反标记，就不会出现这一点问题

但本着求真务实的精神，我们在看一眼先下传取反标记，再下传覆盖标记的情况：

唉？好像在刚才的取反操作中留不留取反标记变得无所谓了，因为不管我传不传取反标记，下传覆盖标记时都会把它清空，传了也相当于没传

发现了吗？这时，我们实际上就已经得到了标记的优先级了：无所谓

虽然听起来多少有点逆天，但事实确实是这样

这时就有人要问了：那为什么要分析懒标记的优先级？

当然，我们的分析并不像得到的结论一样没用，分析中的假设告诉我们，我们进行修改操作的打标记问题，应当随着我们决定的优先级的顺序而定，也就是说，之所以需要考虑懒标记的优先级问题，正是为操作时的细节处理做准备的

其实，如果不考虑一些奇奇怪怪的错误的话，可能大部分的懒标记之间都是无所谓优先级的（来自蒟蒻的短浅观点），比如覆盖标记和加法标记，还有今天的覆盖和取反，只是不同的优先级下，操作的一些细节处理是不同的

但是，我们还知道一个常识：乘法标记的优先级必定高于加法标记，所以，我今天就来仔细分析一下其中的道理（算是对当时不求甚解的弥补吧）：

一样的，还是先考虑操作时标记间的互相影响

如果现在一个结点$u$已经有一个加标记$add_u$，实际的值是$val_u$（注意结点的加标记不是给自己用的，而是给它的两个儿子用的，因此$val_u$就是更新后正确的值），那么我们设它两个儿子结点未更新的值分别是$val_{ls}$和$val_{rs}$，那么它们实际的值应为$val_{ls}+add_u$和$val_{rs}+add_u$。此时要给结点$u$添加一个乘标记$mul_u$，并更新$val_u$，那么它对加标记会产生什么影响呢？

根据打标记的先后顺序，那么左右儿子的正确的值就是$(val_{ls/rs}+add_u)\times mul_u$

假设先下传加标记再下传乘标记，那么左右儿子的值就变成了$(val_{ls/rs}+add_u)\times mul_u$，这说明乘标记对加标记没有影响。因为如果添加乘标记时，还对原先的加标记产生了影响，此时的加标记我们不妨记为$add_u'$，下传时根据我们的假设，左右儿子的值变成了$(val_{ls/rs}+add_u')\times mul_u$，发现唯一能保证更新后值的正确性的影响，只有不影响（可能有点绕口，但这是蒟蒻能想到的最形象的表达了）

假设先下传乘标记再下传加标记，那么左右儿子的值就变成了$val_{ls/rs}\times mul_u + add_u$，发现并不等于上面正确的$(val_{ls/rs}+add_u)\times mul_u=val_{ls/rs}\times mul_u + add_u \times mul_u$。显然，这时乘标记必须对加标记产生影响，也就是让$add_u'=add_u \times mul_u$，然后在下传时使得$val_{ls/rs}\times mul_u + add_u'=val_{ls/rs}\times mul_u + add_u \times mul_u$，才能保证更新后的值依然是正确的

好了，现在乘标记对加标记的影响我们讨论完了，轮到加标记对乘标记的影响了

还是有一个结点$u$，已经有一个乘标记$mul_u$，实际的值是$val_u$（这里的实际值和上面一样，也是更新后的值），依然设它两个儿子结点的未更新的值分别是$val_{ls}$和$val_{rs}$，那么它们实际的值应为$val_{ls}\times mul_u$和$val_{rs}\times mul_u$。此时要给结点$u$添加一个加标记$add_u$，思考其会对乘标记产生的影响

仍然用最笨（但真的好用）的办法，假设

和刚才一样，根据打标记的先后顺序，左右儿子正确的值应为$val_{ls/rs}\times mul_u + add_u$

假设先下传加标记再下传乘标记，那么左右儿子的值变成了$(val_{ls/rs}+add_u)\times mul_u$，这显然是不对的。为了保证更新的正确性，我们必须通过一些操作来把修正。既然我们现在在想加标记对乘标记的影响，那我们就优先考虑影响乘标记来修正。考虑把错误的值拆开，拿到$val_{ls/rs}\times mul_u + add_u \times mul_u$，比对系数，得到一个结论，$mul_u$不能被影响。~~学过数学的都知道，~~作为当前最高次项的系数，我们不能乱动这个$mul_u$，似乎到头来不仅没有把乘标记影响成什么样子，反而把自己搭进去了，因为为了修正错误，$add_u'$就必须是$\frac{add_u}{mul_u}$，才能使更新后的值等于真正的值。但：

不管黑猫白猫，能捉老鼠的就是好猫 ——邓小平

所以搭进去就搭进去吧，能保证正确性就行

假设先下传乘标记再下传加标记，那么左右儿子的值变成了$val_{ls/rs}\times mul_u + add_u$，与正确值完全相同，所以这时加标记对乘标记没有影响

综上：

如果加标记的优先级高于乘标记，即先下传加标记再下传乘标记，那么乘标记对加标记没有影响，加标记对乘标记的“影响”是让自己变成$\frac{add_u}{mul_u}$（不是哥们，我写这句话的时候真没绷住）

如果乘标记的优先级高于加标记，即先下传乘标记再下传加标记，那么乘标记对加标记的影响是使加标记变为$add_u\times mul_u$，加标记对乘标记没有影响

唉？好像也是都可以的？不确定，再看看——嘶……好像……

行了，别好像了， 问题就在于$\frac{add_u}{mul_u}$的精度。众所周知，c++是不能存分数的，而所有语言的浮点数都有精度误差，所以$\frac{add_u}{mul_u}$只有在保证整除的情况下是准确的，那什么时候一定整除呢？答案是：没有乘法的时候……（相当于分母恒为1）

所以，为了避免这一奇奇怪怪的问题有可能导致的奇奇怪怪的错误，我们在既有乘法又有加法的线段树中，总是让乘标记的优先级高于加标记

好啦，分析完啦，发现了吗？只要排除这些奇怪的问题，或者c++的功能在强大一点，标记的优先级是无所谓的吧

Code

呼——冗长的分析终于结束了，上代码~

$ps$：线段树每个人的码风都不一样，主要的还是思路哦~

覆盖标记优先级高于取反标记版

    #include<bits/stdc++.h>
    
    using namespace std;
    
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    #define mid ((l + r) >> 1)
    
    const int N = 1e5 + 10;
    int n, m;
    int a[N];
    
    struct Node {
        int len, L_len_1, R_len_1, Max_len_1;
    };
    
    struct {
       struct {
           int len{}, cnt_1{}, L_len_1{}, R_len_1{}, Max_len_1{};
           int L_len_0{}, R_len_0{}, Max_len_0{};
           int cover{}, reverse{};
       } t[N << 2];
    
       inline void up(int u) {
           t[u].cnt_1 = t[ls].cnt_1 + t[rs].cnt_1;
           t[u].Max_len_1 = max(max(t[ls].Max_len_1, t[rs].Max_len_1), t[ls].R_len_1 + t[rs].L_len_1);
           t[u].L_len_1 = (t[ls].L_len_1 == t[ls].len ? t[ls].L_len_1 + t[rs].L_len_1 : t[ls].L_len_1);
           t[u].R_len_1 = (t[rs].R_len_1 == t[rs].len ? t[rs].R_len_1 + t[ls].R_len_1 : t[rs].R_len_1);
           t[u].Max_len_0 = max(max(t[ls].Max_len_0, t[rs].Max_len_0), t[ls].R_len_0 + t[rs].L_len_0);
           t[u].L_len_0 = (t[ls].L_len_0 == t[ls].len ? t[ls].L_len_0 + t[rs].L_len_0 : t[ls].L_len_0);
           t[u].R_len_0 = (t[rs].L_len_0 == t[rs].len ? t[rs].R_len_0 + t[ls].R_len_0 : t[rs].R_len_0);
       }
    
       inline void blt(int u, int l, int r) {
           if (l == r) {
               t[u] = {1, a[l] == 1, a[l] == 1, a[l] == 1, a[l] == 1,
                       a[l] == 0, a[l] == 0, a[l] == 0,
                       -1, 0};
               return;
           }
           t[u].len = r - l + 1, t[u].cover = -1, t[u].reverse = 0;
           blt(ls, l, mid), blt(rs, mid + 1, r), up(u);
       }
    
       inline void Cover(int u, int x) {
           if (x) {
               t[u].cnt_1 = t[u].L_len_1 = t[u].R_len_1 = t[u].Max_len_1 = t[u].len;
               t[u].L_len_0 = t[u].R_len_0 = t[u].Max_len_0 = t[u].reverse = 0;
           } else {
               t[u].cnt_1 = t[u].L_len_1 = t[u].R_len_1 = t[u].Max_len_1 = t[u].reverse = 0;
               t[u].L_len_0 = t[u].R_len_0 = t[u].Max_len_0 = t[u].len;
           }
           t[u].cover = x;
       }
    
       inline void Reverse(int u) {
           swap(t[u].L_len_1, t[u].L_len_0);
           swap(t[u].R_len_1, t[u].R_len_0);
           swap(t[u].Max_len_1, t[u].Max_len_0);
           t[u].cnt_1 = t[u].len - t[u].cnt_1;
           if (~t[u].cover)
               t[u].cover ^= 1;
           else//这个时候的取反标记不能乱加哦~
               t[u].reverse ^= 1;
       }
    
       inline void down(int u) {
           if (~t[u].cover)//先下传覆盖标记
               Cover(ls, t[u].cover), Cover(rs, t[u].cover), t[u].cover = -1;
           if (t[u].reverse)//再下传取反标记
               Reverse(ls), Reverse(rs), t[u].reverse = 0;
       }
    
       inline void Cover(int u, int l, int r, int ql, int qr, int x) {
           if (l > qr || r < ql)
               return;
           if (l >= ql && r <= qr) {
               Cover(u, x);
               return;
           }
           down(u);
           Cover(ls, l, mid, ql, qr, x), Cover(rs, mid + 1, r, ql, qr, x), up(u);
       }
    
       inline void Reverse(int u, int l, int r, int ql, int qr) {
           if (l > qr || r < ql)
               return;
           if (l >= ql && r<= qr) {
               Reverse(u);
               return;
           }
           down(u);
           Reverse(ls, l, mid, ql, qr), Reverse(rs, mid + 1, r, ql, qr), up(u);
       }
    
       inline int Cnt_Query(int u, int l, int r, int ql, int qr) {
           if (l > qr || r < ql)
               return 0;
           if (l >= ql && r <= qr)
               return t[u].cnt_1;
           down(u);
           return Cnt_Query(ls, l, mid, ql, qr) + Cnt_Query(rs, mid + 1, r, ql, qr);
       }
    
       inline Node Len_Query(int u, int l, int r, int ql, int qr) {
           if (l > qr || r < ql)
               return {0, 0, 0, 0};
           if (l >= ql && r <= qr)
               return {t[u].len, t[u].L_len_1, t[u].R_len_1, t[u].Max_len_1};
           down(u);
           Node L = Len_Query(ls, l, mid, ql, qr), R = Len_Query(rs, mid + 1, r, ql, qr);
           return {L.len + R.len,
                   (L.L_len_1 == L.len ? L.L_len_1 + R.L_len_1 : L.L_len_1),
                   (R.R_len_1 == R.len ? R.R_len_1 + L.R_len_1 : R.R_len_1),
                   max(max(L.Max_len_1, R.Max_len_1), L.R_len_1 + R.L_len_1)};
       }
    
    } T;
    
    signed main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        T.blt(1, 1, n);
        while (m--) {
            int op, l, r;
            cin >> op >> l >> r, l++, r++;
            if (op == 0)
                T.Cover(1, 1, n, l, r, 0);
            else if (op == 1)
                T.Cover(1, 1, n, l, r, 1);
            else if (op == 2)
                T.Reverse(1, 1, n, l, r);
            else if (op == 3)
                cout << T.Cnt_Query(1, 1, n, l, r) << "\n";
            else {
                Node ans = T.Len_Query(1, 1, n, l, r);
                cout << ans.Max_len_1 << "\n";
            }
        }
        return 0;
    }

取反标记优先级高于覆盖标记，且留取反标记版

    #include<bits/stdc++.h>
    
    using namespace std;
    
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    #define mid ((l + r) >> 1)
    
    const int N = 1e5 + 10;
    int n, m;
    int a[N];
    
    struct Node {
        int len, L_len_1, R_len_1, Max_len_1;
    };
    
    struct {
       struct {
           int len{}, cnt_1{}, L_len_1{}, R_len_1{}, Max_len_1{};
           int L_len_0{}, R_len_0{}, Max_len_0{};
           int cover{}, reverse{};
       } t[N << 2];
    
       inline void up(int u) {
           t[u].cnt_1 = t[ls].cnt_1 + t[rs].cnt_1;
           t[u].Max_len_1 = max(max(t[ls].Max_len_1, t[rs].Max_len_1), t[ls].R_len_1 + t[rs].L_len_1);
           t[u].L_len_1 = (t[ls].L_len_1 == t[ls].len ? t[ls].L_len_1 + t[rs].L_len_1 : t[ls].L_len_1);
           t[u].R_len_1 = (t[rs].R_len_1 == t[rs].len ? t[rs].R_len_1 + t[ls].R_len_1 : t[rs].R_len_1);
           t[u].Max_len_0 = max(max(t[ls].Max_len_0, t[rs].Max_len_0), t[ls].R_len_0 + t[rs].L_len_0);
           t[u].L_len_0 = (t[ls].L_len_0 == t[ls].len ? t[ls].L_len_0 + t[rs].L_len_0 : t[ls].L_len_0);
           t[u].R_len_0 = (t[rs].L_len_0 == t[rs].len ? t[rs].R_len_0 + t[ls].R_len_0 : t[rs].R_len_0);
       }
    
       inline void blt(int u, int l, int r) {
           if (l == r) {
               t[u] = {1, a[l] == 1, a[l] == 1, a[l] == 1, a[l] == 1,
                       a[l] == 0, a[l] == 0, a[l] == 0,
                       -1, 0};
               return;
           }
           t[u].len = r - l + 1, t[u].cover = -1, t[u].reverse = 0;
           blt(ls, l, mid), blt(rs, mid + 1, r), up(u);
       }
    
       inline void Cover(int u, int x) {
           if (x) {
               t[u].cnt_1 = t[u].L_len_1 = t[u].R_len_1 = t[u].Max_len_1 = t[u].len;
               t[u].L_len_0 = t[u].R_len_0 = t[u].Max_len_0 = t[u].reverse = 0;
           } else {
               t[u].cnt_1 = t[u].L_len_1 = t[u].R_len_1 = t[u].Max_len_1 = t[u].reverse = 0;
               t[u].L_len_0 = t[u].R_len_0 = t[u].Max_len_0 = t[u].len;
           }
           t[u].cover = x;
       }
    
       inline void Reverse(int u) {
           swap(t[u].L_len_1, t[u].L_len_0);
           swap(t[u].R_len_1, t[u].R_len_0);
           swap(t[u].Max_len_1, t[u].Max_len_0);
           t[u].cnt_1 = t[u].len - t[u].cnt_1;
           if (~t[u].cover)
               t[u].cover ^= 1;
           t[u].reverse ^= 1;//怎么标都能过~
       }
    
       inline void down(int u) {
           if (t[u].reverse)//先下传取反标记
               Reverse(ls), Reverse(rs), t[u].reverse = 0;
           if (~t[u].cover)//再下传覆盖标记
               Cover(ls, t[u].cover), Cover(rs, t[u].cover), t[u].cover = -1;
       }
    
       inline void Cover(int u, int l, int r, int ql, int qr, int x) {
           if (l > qr || r < ql)
               return;
           if (l >= ql && r <= qr) {
               Cover(u, x);
               return;
           }
           down(u);
           Cover(ls, l, mid, ql, qr, x), Cover(rs, mid + 1, r, ql, qr, x), up(u);
       }
    
       inline void Reverse(int u, int l, int r, int ql, int qr) {
           if (l > qr || r < ql)
               return;
           if (l >= ql && r<= qr) {
               Reverse(u);
               return;
           }
           down(u);
           Reverse(ls, l, mid, ql, qr), Reverse(rs, mid + 1, r, ql, qr), up(u);
       }
    
       inline int Cnt_Query(int u, int l, int r, int ql, int qr) {
           if (l > qr || r < ql)
               return 0;
           if (l >= ql && r <= qr)
               return t[u].cnt_1;
           down(u);
           return Cnt_Query(ls, l, mid, ql, qr) + Cnt_Query(rs, mid + 1, r, ql, qr);
       }
    
       inline Node Len_Query(int u, int l, int r, int ql, int qr) {
           if (l > qr || r < ql)
               return {0, 0, 0, 0};
           if (l >= ql && r <= qr)
               return {t[u].len, t[u].L_len_1, t[u].R_len_1, t[u].Max_len_1};
           down(u);
           Node L = Len_Query(ls, l, mid, ql, qr), R = Len_Query(rs, mid + 1, r, ql, qr);
           return {L.len + R.len,
                   (L.L_len_1 == L.len ? L.L_len_1 + R.L_len_1 : L.L_len_1),
                   (R.R_len_1 == R.len ? R.R_len_1 + L.R_len_1 : R.R_len_1),
                   max(max(L.Max_len_1, R.Max_len_1), L.R_len_1 + R.L_len_1)};
       }
    
    } T;
    
    signed main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        T.blt(1, 1, n);
        while (m--) {
            int op, l, r;
            cin >> op >> l >> r, l++, r++;
            if (op == 0)
                T.Cover(1, 1, n, l, r, 0);
            else if (op == 1)
                T.Cover(1, 1, n, l, r, 1);
            else if (op == 2)
                T.Reverse(1, 1, n, l, r);
            else if (op == 3)
                cout << T.Cnt_Query(1, 1, n, l, r) << "\n";
            else {
                Node ans = T.Len_Query(1, 1, n, l, r);
                cout << ans.Max_len_1 << "\n";
            }
        }
        return 0;
    }

取反标记优先级高于覆盖标记，且不留取反标记版

#include<bits/stdc++.h>

using namespace std;

#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

const int N = 1e5 + 10;
int n, m;
int a[N];

struct Node {
    int len, L_len_1, R_len_1, Max_len_1;
};

struct {
   struct {
       int len{}, cnt_1{}, L_len_1{}, R_len_1{}, Max_len_1{};
       int L_len_0{}, R_len_0{}, Max_len_0{};
       int cover{}, reverse{};
   } t[N << 2];

   inline void up(int u) {
       t[u].cnt_1 = t[ls].cnt_1 + t[rs].cnt_1;
       t[u].Max_len_1 = max(max(t[ls].Max_len_1, t[rs].Max_len_1), t[ls].R_len_1 + t[rs].L_len_1);
       t[u].L_len_1 = (t[ls].L_len_1 == t[ls].len ? t[ls].L_len_1 + t[rs].L_len_1 : t[ls].L_len_1);
       t[u].R_len_1 = (t[rs].R_len_1 == t[rs].len ? t[rs].R_len_1 + t[ls].R_len_1 : t[rs].R_len_1);
       t[u].Max_len_0 = max(max(t[ls].Max_len_0, t[rs].Max_len_0), t[ls].R_len_0 + t[rs].L_len_0);
       t[u].L_len_0 = (t[ls].L_len_0 == t[ls].len ? t[ls].L_len_0 + t[rs].L_len_0 : t[ls].L_len_0);
       t[u].R_len_0 = (t[rs].L_len_0 == t[rs].len ? t[rs].R_len_0 + t[ls].R_len_0 : t[rs].R_len_0);
   }

   inline void blt(int u, int l, int r) {
       if (l == r) {
           t[u] = {1, a[l] == 1, a[l] == 1, a[l] == 1, a[l] == 1,
                   a[l] == 0, a[l] == 0, a[l] == 0,
                   -1, 0};
           return;
       }
       t[u].len = r - l + 1, t[u].cover = -1, t[u].reverse = 0;
       blt(ls, l, mid), blt(rs, mid + 1, r), up(u);
   }

   inline void Cover(int u, int x) {
       if (x) {
           t[u].cnt_1 = t[u].L_len_1 = t[u].R_len_1 = t[u].Max_len_1 = t[u].len;
           t[u].L_len_0 = t[u].R_len_0 = t[u].Max_len_0 = t[u].reverse = 0;
       } else {
           t[u].cnt_1 = t[u].L_len_1 = t[u].R_len_1 = t[u].Max_len_1 = t[u].reverse = 0;
           t[u].L_len_0 = t[u].R_len_0 = t[u].Max_len_0 = t[u].len;
       }
       t[u].cover = x;
   }

   inline void Reverse(int u) {
       swap(t[u].L_len_1, t[u].L_len_0);
       swap(t[u].R_len_1, t[u].R_len_0);
       swap(t[u].Max_len_1, t[u].Max_len_0);
       t[u].cnt_1 = t[u].len - t[u].cnt_1;
       if (~t[u].cover)
           t[u].cover ^= 1;
       else
           t[u].reverse ^= 1;
   }

   inline void down(int u) {
       if (t[u].reverse)
           Reverse(ls), Reverse(rs), t[u].reverse = 0;
       if (~t[u].cover)
           Cover(ls, t[u].cover), Cover(rs, t[u].cover), t[u].cover = -1;
   }

   inline void Cover(int u, int l, int r, int ql, int qr, int x) {
       if (l > qr || r < ql)
           return;
       if (l >= ql && r <= qr) {
           Cover(u, x);
           return;
       }
       down(u);
       Cover(ls, l, mid, ql, qr, x), Cover(rs, mid + 1, r, ql, qr, x), up(u);
   }

   inline void Reverse(int u, int l, int r, int ql, int qr) {
       if (l > qr || r < ql)
           return;
       if (l >= ql && r<= qr) {
           Reverse(u);
           return;
       }
       down(u);
       Reverse(ls, l, mid, ql, qr), Reverse(rs, mid + 1, r, ql, qr), up(u);
   }

   inline int Cnt_Query(int u, int l, int r, int ql, int qr) {
       if (l > qr || r < ql)
           return 0;
       if (l >= ql && r <= qr)
           return t[u].cnt_1;
       down(u);
       return Cnt_Query(ls, l, mid, ql, qr) + Cnt_Query(rs, mid + 1, r, ql, qr);
   }

   inline Node Len_Query(int u, int l, int r, int ql, int qr) {
       if (l > qr || r < ql)
           return {0, 0, 0, 0};
       if (l >= ql && r <= qr)
           return {t[u].len, t[u].L_len_1, t[u].R_len_1, t[u].Max_len_1};
       down(u);
       Node L = Len_Query(ls, l, mid, ql, qr), R = Len_Query(rs, mid + 1, r, ql, qr);
       return {L.len + R.len,
               (L.L_len_1 == L.len ? L.L_len_1 + R.L_len_1 : L.L_len_1),
               (R.R_len_1 == R.len ? R.R_len_1 + L.R_len_1 : R.R_len_1),
               max(max(L.Max_len_1, R.Max_len_1), L.R_len_1 + R.L_len_1)};
   }

} T;

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    T.blt(1, 1, n);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r, l++, r++;
        if (op == 0)
            T.Cover(1, 1, n, l, r, 0);
        else if (op == 1)
            T.Cover(1, 1, n, l, r, 1);
        else if (op == 2)
            T.Reverse(1, 1, n, l, r);
        else if (op == 3)
            cout << T.Cnt_Query(1, 1, n, l, r) << "\n"；
        else {
            Node ans = T.Len_Query(1, 1, n, l, r);
            cout << ans.Max_len_1 << "\n";
        }
    }
    return 0;
}

后记

其实这篇文章主要写的并不是序列操作这道题，而是蒟蒻个人对于线段树懒标记的新理解和一点点顿悟，为了助其它还困顿在线段树标记优先级问题中的$Coder$一臂之力（蒟蒻在网上一直没有找到一篇很详细的题解，因此难受了许久，所以今天弄懂了以后，就立马写了一份比较详细的题解）

本文对于原题的分析其实还不如对加乘标记优先级的分析详细，如果有不太清楚的建议自证下去好好整理一下思路哦~

不过对于各位巨佬，这些东西应该是很一眼的吧

苦于没钱开博客，被迫在洛谷班门弄斧

写在最后

$Praying~that~your~future~life~will~always~be~ accompanied~by~the~magic~of~happiness.$

祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。