To boldly go where no one has gone before.

【学习笔记】线段树

2019-03-02 12:06:33


例题 P2023

就是这个线段树2的模板,我总是没有AC过,这次终于是AC了!

最需要注意的是:在乘的时候,加法的$lazytag$也必须跟着更新;$pushdown$的时候,加法的$lazytag$也必须跟着更新,不然就无法连续维护加操作和乘操作。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MAXN = 100010;

struct SEGTREE {
    int l, r;
    LL v, add, mul;
} segtree[MAXN<<2];

int n, p, m;
LL a[MAXN];

void build_tree(int num, int l, int r) {
    segtree[num].l = l;
    segtree[num].r = r;
    segtree[num].add = 0;
    segtree[num].mul = 1;
    if(l == r) {
        segtree[num].v = (LL)a[l] % p;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(num<<1, l, mid);
    build_tree(num<<1|1, mid+1, r);
    segtree[num].v = (segtree[num<<1].v + segtree[num<<1|1].v) % p;
    return;
}

void pushdown(int num) {
    int lson = num<<1, rson = num<<1|1;
    segtree[lson].v = (segtree[lson].v * segtree[num].mul + (segtree[num].add * (segtree[lson].r - segtree[lson].l + 1))) % p;
    segtree[rson].v = (segtree[rson].v * segtree[num].mul + (segtree[num].add * (segtree[rson].r - segtree[rson].l + 1))) % p;
    segtree[lson].add = (segtree[lson].add * segtree[num].mul + segtree[num].add) % p;
    segtree[rson].add = (segtree[rson].add * segtree[num].mul + segtree[num].add) % p;
    segtree[lson].mul = (segtree[lson].mul * segtree[num].mul) % p;
    segtree[rson].mul = (segtree[rson].mul * segtree[num].mul) % p;
    segtree[num].add = 0;
    segtree[num].mul = 1;
    return;
}

void edit_tree(bool add, int num, int l, int r, int c) {
    int ll = segtree[num].l, rr = segtree[num].r;
    if(add) {
        if(ll >= l && rr <= r) {
            segtree[num].v = (segtree[num].v + (c * (rr - ll + 1))) % p;
            segtree[num].add = (segtree[num].add + c) % p;
            return;
        }
        pushdown(num);
        int mid = (ll + rr) >> 1;
        if(l <= mid)
            edit_tree(add, num<<1, l, r, c);
        if(r > mid)
            edit_tree(add, num<<1|1, l, r, c);
        segtree[num].v = (segtree[num<<1].v + segtree[num<<1|1].v) % p;
    } else {
        if(ll >= l && rr <= r) {
            segtree[num].v = (segtree[num].v * c) % p;
            segtree[num].mul = (segtree[num].mul * c) % p;
            segtree[num].add = (segtree[num].add * c) % p;
            return;
        }
        pushdown(num);
        int mid = (ll + rr) >> 1;
        if(l <= mid)
            edit_tree(add, num<<1, l, r, c);
        if(r > mid)
            edit_tree(add, num<<1|1, l, r, c);
        segtree[num].v = (segtree[num<<1].v + segtree[num<<1|1].v) % p;
    }
    return;
}

LL query(int num, int l, int r) {
    int ll = segtree[num].l, rr = segtree[num].r;
    if(ll >= l && rr <= r)
        return segtree[num].v % p;
    pushdown(num);
    int mid = (ll + rr) >> 1;
    LL sum = 0;
    if(l <= mid)
        sum = (query(num<<1, l, r) + sum) % p;
    if(r > mid)
        sum = (query(num<<1|1, l, r) + sum) % p;
    return sum;
}

int main() {
    scanf("%d%d", &n, &p);
    for(int i=1; i<=n; i++)
        scanf("%lli", &a[i]);
    build_tree(1, 1, n);
    int opt, t, g, c;
    scanf("%d", &m);
    while(m--) {
        scanf("%d", &opt);
        switch(opt) {
            case 1: {
                scanf("%d%d%d", &t, &g, &c);
                edit_tree(false, 1, t, g, c);
                break;
            }
            case 2: {
                scanf("%d%d%d", &t, &g, &c);
                edit_tree(true, 1, t, g, c);
                break;
            }
            case 3: {
                scanf("%d%d", &t, &g);
                printf("%lli\n", query(1, t, g)%p);
                break;
            }
        }
    }
    return 0;
}

易错点更新

$edit\_tree$以后记得合并儿子信息!

$pushdown$及$edit\_tree$时记得要把$tag$乘上区间长


线段树维护区间修改/单点修改/区间最大值

例题 P4315

恶心死了,查半天错才知道自己错在哪里。

这里的线段树维护了两个懒标记:$tree[x].tag$以及$tree[x].c$。$tree[x].tag$维护的是区间加,而$tree[x].c$维护的是区间修改。在$pushdown$的时候就要慎重考虑这两个玩意儿的顺序了,结论是:

先看$\textbf{tree[x].c}$,再看$\textbf{tree[x].tag}$。

注意: 在$cover(l,r,c)$的时候,会使当前$tree[x].tag=0$,这也就是说肯定是在一次$\textbf{cover(l,r,c)}$操作之后,出现的$\textbf{tree[x].tag}$才会对线段树造成修改,因此在$pushdown$的时候,如果发生了$cover(l,r,c)$操作,即$tree[x].c\neq-1$,一定是先把$tree[x].c$下传,将两儿子的$tree[x].tag$清空,再把$tree[x].tag$信息下传。

此思路非常重要,正确决定线段树$lazytag$的下传顺序才不会懒出毛病。

inline void pushdown(int x) {
    if(~tree[x].c) {
        tree[x<<1].max = tree[x<<1|1].max = tree[x].c;
        tree[x<<1].c = tree[x<<1|1].c = tree[x].c;
        tree[x<<1].tag = tree[x<<1|1].tag = 0;
        tree[x].c = -1;
    }
    if(tree[x].tag) {
        tree[x<<1].max += tree[x].tag;
        tree[x<<1|1].max += tree[x].tag;
        tree[x<<1].tag += tree[x].tag;
        tree[x<<1|1].tag += tree[x].tag;
        tree[x].tag = 0;
    }
    return;
}

相应地,我们已经决定了$lazytag$的下传顺序,那么$cover(l,r,c)$和$add(l,r,c)$也要按照这个规则来打懒标记,也就是说 $\textbf{cover(l,r,c)}$的时候需要把$\textbf{tree[x].tag=0}$ ,而$add(l,r,c)$则不需要做出调整。

inline void cover(int x, int l, int r, int c) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].max = tree[x].c = c;
        tree[x].tag = 0;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        cover(x<<1, l, r, c);
    if(r > mid)
        cover(x<<1|1, l, r, c);
    pushup(x);
    return;
}

inline void add(int x, int l, int r, int c) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].max += c;
        tree[x].tag += c;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        add(x<<1, l, r, c);
    if(r > mid)
        add(x<<1|1, l, r, c);
    pushup(x);
    return;
}

谨记:慎重考虑懒标记的下传顺序、修改时打懒标记的规则!


完整代码

//code
inline void pushdown(int x) {
    if(~tree[x].c) {
        tree[x<<1].max = tree[x<<1|1].max = tree[x].c;
        tree[x<<1].c = tree[x<<1|1].c = tree[x].c;
        tree[x<<1].tag = tree[x<<1|1].tag = 0;
        tree[x].c = -1;
    }
    if(tree[x].tag) {
        tree[x<<1].max += tree[x].tag;
        tree[x<<1|1].max += tree[x].tag;
        tree[x<<1].tag += tree[x].tag;
        tree[x<<1|1].tag += tree[x].tag;
        tree[x].tag = 0;
    }
    return;
}

inline void pushup(int x) {
    tree[x].max = max(tree[x<<1].max, tree[x<<1|1].max);
    return;
}

inline void build_tree(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    tree[x].tag = 0, tree[x].c = -1;
    if(l == r) {
        tree[x].max = w[rev[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(x<<1, l, mid);
    build_tree(x<<1|1, mid + 1, r);
    pushup(x);
    return;
}

inline void cover(int x, int l, int r, int c) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].max = tree[x].c = c;
        tree[x].tag = 0;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        cover(x<<1, l, r, c);
    if(r > mid)
        cover(x<<1|1, l, r, c);
    pushup(x);
    return;
}

inline void add(int x, int l, int r, int c) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].max += c;
        tree[x].tag += c;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        add(x<<1, l, r, c);
    if(r > mid)
        add(x<<1|1, l, r, c);
    pushup(x);
    return;
}

inline int query(int x, int l, int r) {
    int res = -INF;
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r)
        return tree[x].max;
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        res = max(res, query(x<<1, l, r));
    if(r > mid)
        res = max(res, query(x<<1|1, l, r));
    return res;
}

例题 P3740

这道题是维护区间染色。具体做法为直接开一个$clr[]$来维护当前区间有没有被完全覆盖。可以知道的是,如果一个海报所处的区间被后来的海报完全覆盖,那么这个海报就没法被看见了。例如: image.png 图中$[3,4]$的这块海拔被遮完了,因此它没法被看见。

考虑将这个过程离线(在线的话可参考树链剖分部分对P2146的题解),那么每次只需要查询当前海报区间是否已经被完全覆盖就可以了。因为根本不需要建树,所以复杂度为稳定$O(logn)$,对付这个数据也足够了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 10, MAXM = 1e3 + 10;
bool clr[MAXN << 2], flag;
int n, m, a[MAXM], b[MAXM], ans = 0;

void pushup(int x) {
    clr[x] = clr[x<<1] & clr[x<<1|1];
}

void edit_tree(int x, int l, int r, int L, int R) {
    if(clr[x])
        return;
    if(L <= l && r <= R) {
        flag = clr[x] = true;
        return;
    }
    int mid = (l + r) >> 1;
    if(L <= mid)
        edit_tree(x<<1, l, mid, L, R);
    if(R > mid)
        edit_tree(x<<1|1, mid + 1, r, L, R);
    pushup(x);
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d %d", &a[i], &b[i]);
    for(int i = m; i; i--) {
        flag = false;
        edit_tree(1, 1, n, a[i], b[i]);
        if(flag)
            ans++;
    }
    printf("%d", ans);
    return 0;
}