跳转至

如何写好懒标记

首先简单的只有一个懒标记的自然不需要要说，这里讨论对于有多个懒标记，并且更复杂度还有懒标记。

时间轴

我们对于每一个懒标记同时记录一个 time ，然后对于同一个位置有多个懒标记的情况就按照标记时间从前往后处理。

这种办法优点是很稳，但是也相对难写。

普通下传

我们如何保证 push_down(p) 时的顺序呢，首先打下懒标记时可以选择 push_down(p) ，因为在这里我们允许多个标记同时存在（否则时间复杂度不正确）。

然后我们把标记分个组，像是 reverse，add 这样的会在前面的基础上继续操作的标记分一组，把像是 assignment ( 赋值 ), 等不在前面基础上的，而是直接覆盖的分成第二组。

然后我们按照先进行第二组，在进行第一组的顺序进行操作。其中需要注意的是第二组的操作进行的操作会覆盖第一组，而第一组不会修改第二组的 tag （这里的 tag 为儿子节点的）。

但是需要注意的是，此时在打下标记时如果属于第二组，那么会直接删除第一组的 tag 。

可能比较绕，参见下面的代码：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
struct SegMentTree {
    #define lc (T[p].ls)
    #define rc (T[p].rs)

    static constexpr int M = N<<2;

    int root, cnt;
    struct Node {
        int ls, rs, len;
        int sum;         // 1 的总数, 是否全为0, 是否全为1
        bool tag0, tag1, rev;      // 0   , 1   , 取反 (标记)
        int cont0, contl0, contr0; // 全部，左边，右边 (连续的0)
        int cont1, contl1, contr1; // 全部，左边，右边 (连续的1)
    }T[M];

    Node push_up(int p, Node lt, Node rt) {
        Node ret={T[p].ls, T[p].rs};
        ret.sum = lt.sum+rt.sum;
        ret.len = lt.len+rt.len;

        ret.contl0 = !lt.cont1 ? lt.len+rt.contl0 : lt.contl0;
        ret.contr0 = !rt.cont1 ? rt.len+lt.contr0 : rt.contr0;
        ret.cont0 = max(lt.contr0+rt.contl0, max(lt.cont0, rt.cont0));

        ret.contl1 = !lt.cont0 ? lt.len+rt.contl1 : lt.contl1;
        ret.contr1 = !rt.cont0 ? rt.len+lt.contr1 : rt.contr1;
        ret.cont1 = max(lt.contr1+rt.contl1, max(lt.cont1, rt.cont1));
        return ret;
    }

    void mak_a0(int p) {
        T[p] = Node {
            lc, rc, T[p].len,
            0,
            1, 0, 0,
            T[p].len, T[p].len, T[p].len,
            0, 0, 0
        };
    }

    void mak_a1(int p) {
        T[p] = Node {
            lc, rc, T[p].len,
            T[p].len,
            0, 1, 0,
            0, 0, 0,
            T[p].len, T[p].len, T[p].len
        };
    }

    void mak_rev(int p) {
        T[p] = Node {
            lc, rc, T[p].len,
            T[p].len-T[p].sum,
            T[p].tag0, T[p].tag1, !T[p].rev,
            T[p].cont1, T[p].contl1, T[p].contr1,
            T[p].cont0, T[p].contl0, T[p].contr0
        };
    }

    void push_down(int p) {
        if(T[p].tag0) mak_a0(lc), mak_a0(rc), T[p].tag0=0;
        if(T[p].tag1) mak_a1(lc), mak_a1(rc), T[p].tag1=0;
        if(T[p].rev)  mak_rev(lc), mak_rev(rc), T[p].rev=0;
    }

    void build(int &p, int l, int r, vector<bool>* v) {
        if(l>r) return ;
        p=++cnt, T[p]={0, 0, r-l+1};
        if(l==r) {
            bool x=v->at(l);
            T[p] = Node {
                0, 0, r-l+1,
                x, 0, 0, 0,
                !x, !x, !x, x, x, x 
            };
            return ;
        }

        int mid=l+r>>1;
        build(lc, l, mid, v), build(rc, mid+1, r, v);
        T[p]=push_up(p, T[lc], T[rc]); 
    }

    void change(int p, int l, int r, int x, int y, int op) {
        if(l>r) return ;

        if(x<=l && r<=y) {
            if(op==0) mak_a0(p);
            if(op==1) mak_a1(p);
            if(op==2) mak_rev(p);
            return ;
        }push_down(p);

        int mid=l+r>>1;
        if(x<=mid) change(lc, l, mid, x, y, op);
        if(y>mid) change(rc, mid+1, r, x, y, op);
        T[p]=push_up(p, T[lc], T[rc]); 
    }

    Node query(int p, int l, int r, int x, int y) {
        assert(l<=r);
        if(x<=l && r<=y) return T[p];

        int mid=l+r>>1;
        push_down(p);
        if(x<=mid && y>mid) return push_up(0, query(lc, l, mid, x, y), query(rc, mid+1, r, x, y));
        else if(x<=mid) return query(lc, l, mid, x, y);
        else return query(rc, mid+1, r, x, y);
    }

    #undef lc
    #undef rc
}T;

但是仍然有一点需要注意的，我们前面一直没有考虑第一组和第一组之间影响的情况，比如乘法和加法，此时需要在初始打上标记时同时影响。

其实整体我们可以理解为在这里 "赋值" 比 "迭代" 操作优先级更高。

总结一下

就是对于每一个懒标记赋予一个优先级。然后在赋予懒标记时优先级高的会影响当前块优先级低的块。但是在 push_down 是按照优先级从高到低的顺序处理，处理时优先级高的会影响优先级低的节点的子节点的懒标记，但是不会影响块本身的其他标记。