2013-team4/code/seg-tree

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
uva 11992
}}}
{{{
#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

template<class T> void takemin(T &a, const T &b) {a = min(a, b);}
template<class T> void takemax(T &a, const T &b) {a = max(a, b);}

const int INF = 2100000000;

void gao(PIII &a, const PIII &b){
    a.first += b.first;
    takemin(a.second.first, b.second.first);
    takemax(a.second.second, b.second.second);
}

struct Segtree{
    struct Node{
        int l, r, m, lch, rch;
        int mi, mx, sum;
        bool setf, addf;
        int setv, addv;
    }node[65536 * 32];

    void set(Node &o, int v){
        if(o.addf){
            o.addf = false;
        }
        o.setf = true;
        o.setv = v;
        o.mi = o.mx = v;
        o.sum = (o.r - o.l + 1) * v;
    }

    void add(Node &o, int v){
        if(o.setf){
            set(o, o.setv + v);
        }
        else{
            if(o.addf) o.addv += v;
            else o.addv = v;
            o.addf = true;
            o.mi += v; o.mx += v;
            o.sum += (o.r - o.l + 1) * v;
        }
    }

    void push_down(Node &o){
        if(o.setf){
            o.setf = false;
            set(node[o.lch], o.setv);
            set(node[o.rch], o.setv);
        }
        else if(o.addf){
            o.addf = false;
            add(node[o.lch], o.addv);
            add(node[o.rch], o.addv);
        }
    }

    void pull_up(Node &o){
        Node &L = node[o.lch], &R = node[o.rch];
        o.mi = min(L.mi, R.mi);
        o.mx = max(L.mx, R.mx);
        o.sum = L.sum + R.sum;
    }

    void build(int rt, int l, int r){
        Node &o = node[rt];
        o.l = l; o.r = r; o.m = (l + r) / 2;
        o.setf = o.addf = false;
        o.mi = o.mx = o.sum = 0;
        if(l < r){
            o.lch = rt * 2;
            o.rch = o.lch + 1;
            build(o.lch, o.l, o.m);
            build(o.rch, o.m + 1, o.r);
        }
    }

    void update(int rt, int l, int r, int v, bool type){
        Node &o = node[rt];
        if(l <= o.l && o.r <= r){
            if(type == true) add(o, v);
            else set(o, v);
            return;
        }
        push_down(o);
        if(l <= o.m) update(o.lch, l, r, v, type);
        if(r >= o.m + 1) update(o.rch, l, r, v, type);
        pull_up(o);
    }

    PIII query(int rt, int l, int r){
        Node &o = node[rt];
        if(l <= o.l && o.r <= r){
            return PIII(o.sum, PII(o.mi, o.mx));
        }
        push_down(o);
        PIII ret = PIII(0, PII(INF, -INF));
        if(l <= o.m) gao(ret, query(o.lch, l, r));
        if(r >= o.m + 1) gao(ret, query(o.rch, l, r));
        return ret;
    }
}tree[21];

int main(){
    int r, c, m;
    while(3 == scanf("%d %d %d", &r, &c, &m)){
        for(int i = 1; i <= r; i++)
            tree[i].build(1, 1, c);
        while(m--){
            int op, x1, x2, y1, y2, v;
            scanf("%d %d %d %d %d", &op, &x1, &y1, &x2, &y2);
            if(op != 3){
                scanf("%d", &v);
                for(int i = x1; i <= x2; i++)
                    tree[i].update(1, y1, y2, v, bool(op == 1));
            }
            else{
                PIII ans = PIII(0, PII(INF, -INF));
                for(int i = x1; i <= x2; i++){
                    gao(ans, tree[i].query(1, y1, y2));
                }
                printf("%d %d %d\n", ans.first, ans.second.first, ans.second.second);
            }
        }
    }
    return 0;
}
}}}

{{{
多个懒标记的线段树
做法：将懒标记规定优先级，每次pushdown的时候根据优先级来pushdown
比如：同时存在3种区间操作：1.整段区间赋值为一个数 2.整段区间加上一个数 3.整段区间乘上一个数
这时候我们规定cover操作的优先级最高，加法和乘法可以利用分配律/结合律同时处理
例子：BZOJ 1798，UVA 11402
}}}

{{{
线段树区间开方
处理方法：每个数一般小于2^32次，也就是说一个数最多开方7次就会变成1(0除外)
于是我们可以暴力开方，每次维护一个区间最大值，当这个区间最大值小于等于1的时候，就不用给这个区间开方了
时间复杂度是log级的
例子：BZOJ 3211，SPOJ GSS4
}}}

{{{
求区间的平方和，或者立方和，或者p次方和(一般p<=3，最大不会超过4)，修改操作包括单点修改和成段修改(有覆盖，加，乘)
处理方法：二项式展开，以平方和为例，成段修改操作只有加法
(A[i]+x)^2=A[i]^2+2*A[i]*x+x^2
观察上面式子，我们知道这棵线段树需要维护ΣA[i]^2和ΣA[i]，这样就好了
例子：SPOJ SEGSQRSS
}}}

uva 11992

#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
template<class T> void takemin(T &a, const T &b) {a = min(a, b);}
template<class T> void takemax(T &a, const T &b) {a = max(a, b);}
const int INF = 2100000000;
void gao(PIII &a, const PIII &b){
    a.first += b.first;
    takemin(a.second.first, b.second.first);
    takemax(a.second.second, b.second.second);
}
struct Segtree{
    struct Node{
        int l, r, m, lch, rch;
        int mi, mx, sum;
        bool setf, addf;
        int setv, addv;
    }node[65536 * 32];
    void set(Node &o, int v){
        if(o.addf){
            o.addf = false;
        }
        o.setf = true;
        o.setv = v;
        o.mi = o.mx = v;
        o.sum = (o.r - o.l + 1) * v;
    }
    void add(Node &o, int v){
        if(o.setf){
            set(o, o.setv + v);
        }
        else{
            if(o.addf) o.addv += v;
            else o.addv = v;
            o.addf = true;
            o.mi += v; o.mx += v;
            o.sum += (o.r - o.l + 1) * v;
        }
    }
    void push_down(Node &o){
        if(o.setf){
            o.setf = false;
            set(node[o.lch], o.setv);
            set(node[o.rch], o.setv);
        }
        else if(o.addf){
            o.addf = false;
            add(node[o.lch], o.addv);
            add(node[o.rch], o.addv);
        }
    }
    void pull_up(Node &o){
        Node &L = node[o.lch], &R = node[o.rch];
        o.mi = min(L.mi, R.mi);
        o.mx = max(L.mx, R.mx);
        o.sum = L.sum + R.sum;
    }
    void build(int rt, int l, int r){
        Node &o = node[rt];
        o.l = l; o.r = r; o.m = (l + r) / 2;
        o.setf = o.addf = false;
        o.mi = o.mx = o.sum = 0;
        if(l < r){
            o.lch = rt * 2;
            o.rch = o.lch + 1;
            build(o.lch, o.l, o.m);
            build(o.rch, o.m + 1, o.r);
        }
    }
    void update(int rt, int l, int r, int v, bool type){
        Node &o = node[rt];
        if(l <= o.l && o.r <= r){
            if(type == true) add(o, v);
            else set(o, v);
            return;
        }
        push_down(o);
        if(l <= o.m) update(o.lch, l, r, v, type);
        if(r >= o.m + 1) update(o.rch, l, r, v, type);
        pull_up(o);
    }
    PIII query(int rt, int l, int r){
        Node &o = node[rt];
        if(l <= o.l && o.r <= r){
            return PIII(o.sum, PII(o.mi, o.mx));
        }
        push_down(o);
        PIII ret = PIII(0, PII(INF, -INF));
        if(l <= o.m) gao(ret, query(o.lch, l, r));
        if(r >= o.m + 1) gao(ret, query(o.rch, l, r));
        return ret;
    }
}tree[21];
int main(){
    int r, c, m;
    while(3 == scanf("%d %d %d", &r, &c, &m)){
        for(int i = 1; i <= r; i++)
            tree[i].build(1, 1, c);
        while(m--){
            int op, x1, x2, y1, y2, v;
            scanf("%d %d %d %d %d", &op, &x1, &y1, &x2, &y2);
            if(op != 3){
                scanf("%d", &v);
                for(int i = x1; i <= x2; i++)
                    tree[i].update(1, y1, y2, v, bool(op == 1));
            }
            else{
                PIII ans = PIII(0, PII(INF, -INF));
                for(int i = x1; i <= x2; i++){
                    gao(ans, tree[i].query(1, y1, y2));
                }
                printf("%d %d %d\n", ans.first, ans.second.first, ans.second.second);
            }
        }
    }
    return 0;
}

多个懒标记的线段树
做法：将懒标记规定优先级，每次pushdown的时候根据优先级来pushdown
比如：同时存在3种区间操作：1.整段区间赋值为一个数 2.整段区间加上一个数 3.整段区间乘上一个数
这时候我们规定cover操作的优先级最高，加法和乘法可以利用分配律/结合律同时处理
例子：BZOJ 1798，UVA 11402

线段树区间开方
处理方法：每个数一般小于2^32次，也就是说一个数最多开方7次就会变成1(0除外)
于是我们可以暴力开方，每次维护一个区间最大值，当这个区间最大值小于等于1的时候，就不用给这个区间开方了
时间复杂度是log级的
例子：BZOJ 3211，SPOJ GSS4

求区间的平方和，或者立方和，或者p次方和(一般p<=3，最大不会超过4)，修改操作包括单点修改和成段修改(有覆盖，加，乘)
处理方法：二项式展开，以平方和为例，成段修改操作只有加法
(A[i]+x)^2=A[i]^2+2*A[i]*x+x^2
观察上面式子，我们知道这棵线段树需要维护ΣA[i]^2和ΣA[i]，这样就好了
例子：SPOJ SEGSQRSS