线段树小姿势

发表于   |   分类于   |     |  

区间合并

SPOJ GSS1

题意

  • 给一个$n$长度的序列,$A[1]…A[n], ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 )$
  • $M$个询问 询问区间内最大连续和

题解

  • 线段树每个节点维护$Lmax,Rmax,maxx,sum$
  • $Lmax$表示从左端点开始的最大连续和 $Rmax$同理 $maxx$不受端点限制 $sum$表示这节点上的总和
  • 转移详见代码
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
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define LL long long
using namespace std;
const int M = 1e5 + 5, INF = 0x3f3f3f3f, mod = 1e9 + 7;
struct segment_tree {
    struct node {
        LL Lmax, Rmax, maxx, sum;
        int L, R;
    } tree[M * 4];
    node up(node a, node b) {
        node res;
        res.L = a.L; res.R = b.R;
        res.Lmax = max(a.Lmax, a.sum + b.Lmax);
        res.Rmax = max(b.Rmax, b.sum + a.Rmax);
        res.maxx = max(res.Lmax, res.Rmax);
        res.maxx = max(max(a.maxx, b.maxx), a.Rmax + b.Lmax);
        res.sum = a.sum + b.sum;
        return res;
    }
    void build(int x, int y, int p, int *A) {
        tree[p].L = x; tree[p].R = y;
        tree[p].Lmax = tree[p].Rmax = tree[p].maxx =-1e18;
        tree[p].sum=0;
        if(x == y) {
            tree[p].Lmax = tree[p].Rmax = tree[p].maxx = tree[p].sum = A[x];
            return;
        }
        int mid = (tree[p].L + tree[p].R) >> 1;
        build(x, mid, p * 2, A);
        build(mid + 1, y, p * 2 + 1, A);
        tree[p] = up(tree[p * 2], tree[p * 2 + 1]);
    }
    node query(int x, int y, int p) {
        if(tree[p].L == x && tree[p].R == y) return tree[p];
        int mid = (tree[p].L + tree[p].R) >> 1;
        if(y <= mid) return query(x, y, p * 2);
        else if(x > mid) return query(x, y, p * 2 + 1);
        else return up(query(x, mid, p * 2), query(mid + 1, y, p * 2 + 1));
    }
} tree;
int A[M];
int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        for(int j = 1; j <= n; j++) scanf("%d", &A[j]);
        tree.build(1, n, 1, A);
        int m;
        scanf("%d", &m);
        while(m--) {
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%d\n", tree.query(a, b, 1).maxx);
        }
    }
    return 0;
}

HDU5316

题意

  • 给一个$n(n<=1e5)$长度的数列有两种操作
  • $1$：修改一个点
  • $2$：查询一个区间,查询一个最大子序列,子序列需满足下标奇偶交替,比方说$1,4,5,6$,或者$4,5,6$

题解

奇偶交替的序列无非四种情况

  • 奇开头偶结尾
  • 奇开头奇结尾
  • 偶开头奇结尾
  • 偶开头偶结尾

然后我就可以存这四个东西了，以$o$表示$odd$，$e$表示$even$
所以我取名就是$oo,ee,oe,eo$
转移详见代码

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
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define LL long long
using namespace std;
const int M = 1e5 + 5, INF = 0x3f3f3f3f, mod = 1e9 + 7;
struct segment_tree {
    struct node {
        //o=odd,e=even
        LL oe, eo, ee, oo;
        int L, R;
    } tree[M * 4];
    node up(node a, node b) {
        node res;
        res.L=a.L;res.R=b.R;
        //注意相接部分的奇偶性应该相反
        res.oo = max(max(a.oo, b.oo), max(a.oo + b.eo, a.oe + b.oo)); 
        res.oe = max(max(a.oe, b.oe), max(a.oo + b.ee, a.oe + b.oe));
        res.eo = max(max(a.eo, b.eo), max(a.eo + b.eo, a.ee + b.oo));
        res.ee = max(max(a.ee, b.ee), max(a.ee + b.oe, a.eo + b.ee));
        return res;
    }
    void build(int x, int y, int p) {
        tree[p].L = x; tree[p].R = y;
        tree[p].oe=tree[p].eo=tree[p].oo=tree[p].ee=-1e18;
        if(x == y) return;
        int mid = (tree[p].L + tree[p].R) >> 1;
        build(x, mid, p * 2);
        build(mid + 1, y, p * 2 + 1);
    }
    node query(int x, int y, int p) {
        if(tree[p].L == x && tree[p].R == y) return tree[p];
        int mid = (tree[p].L + tree[p].R) >> 1;
        if(y <= mid) return query(x, y, p * 2);
        else if(x > mid) return query(x, y, p * 2 + 1);
        else return up(query(x, mid, p * 2), query(mid + 1, y, p * 2 + 1));
    }
    void update(int x, int y, int p) {
        if(x == tree[p].L && x == tree[p].R) {
            tree[p].oo = tree[p].ee = -1e18;
            if(x % 2) tree[p].oo = y;
            else tree[p].ee = y;
            return;
        }
        int mid = (tree[p].L + tree[p].R) >> 1;
        if(x <= mid) update(x, y, p * 2);
        else update(x, y, p * 2 + 1);
        tree[p] = up(tree[p * 2], tree[p * 2 + 1]);
    }
} tree;
int A[M];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        tree.build(1, n, 1);
        for(int j = 1; j <= n; j++) {
            scanf("%d", &A[j]);
            tree.update(j, A[j], 1);
        }
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if(a == 0) {
                auto t = tree.query(b, c, 1);
                printf("%I64d\n", max(max(t.oo, t.ee), max(t.oe, t.eo)));
            } else tree.update(b, c, 1);
        }
    }
    return 0;
}

标记合并

uva11402

题意

  • 给一个01串，每次有四种操作:
  • 1:把区间置1
  • 2:把区间置0
  • 3:区间内的01翻转
  • 4:查询区间1的个数

题解

T神博客

我的代码

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
115
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define LL long long
using namespace std;
const int M = 2e6 + 5, INF = 0x3f3f3f3f, mod = 1e9 + 7;
struct segment_tree {
    struct node {
        int L, R, tag, sum;
    } tree[M * 4];
    void up(int p) {
        node &lson = tree[p * 2], &rson = tree[p * 2 + 1];
        tree[p].sum = lson.sum + rson.sum;
    }
    void get(node& a, int tag) {
        if(tag == 1) a.sum = a.R - a.L + 1;
        if(tag == 2) a.sum = 0;
        if(tag == 3) a.sum = a.R - a.L + 1 - a.sum;
    }
    void combinetag(int a, int &b) {
        int flag = 0;
        if(a == 1) b = 1;
        if(a == 2) b = 2;
        if(a == 3) {
            if(b == 0) b = 3;
            else if(b == 3) b = 0;
            else if(b == 1) b = 2;
            else b = 1;
        }
    }
    void down(int p) {
        if(!tree[p].tag) return;
        int &tag = tree[p].tag;
        node& lson = tree[p * 2], &rson = tree[p * 2 + 1];
        get(lson, tag);
        get(rson, tag);
        combinetag(tag, lson.tag);
        combinetag(tag, rson.tag);
        tag = 0;
    }
    void build(int x, int y, int p, string &s) {
        tree[p].L = x; tree[p].R = y; tree[p].tag = tree[p].sum = 0;
        if(x == y) {
            tree[p].sum = s[x - 1] - '0';
            return;
        }
        int mid = (tree[p].L + tree[p].R) >> 1;
        build(x, mid, p * 2, s);
        build(mid + 1, y, p * 2 + 1, s);
        up(p);
    }
    int query(int x, int y, int p) {
        if(tree[p].L == x && tree[p].R == y) return tree[p].sum;
        down(p);
        int mid = (tree[p].L + tree[p].R) >> 1;
        int res;
        if(y <= mid) res = query(x, y, p * 2);
        else if(x > mid) res = query(x, y, p * 2 + 1);
        else res = query(x, mid, p * 2) + query(mid + 1, y, p * 2 + 1);
        up(p);
        return res;
    }
    void update(int x, int y, int z, int p) {
        if(x == tree[p].L && y == tree[p].R) {
            get(tree[p], z);
            combinetag(z, tree[p].tag);
            return;
        }
        down(p);
        int mid = (tree[p].L + tree[p].R) >> 1;
        if(y <= mid) update(x, y, z, p * 2);
        else if(x > mid) update(x, y, z, p * 2 + 1);
        else update(x, mid, z, p * 2), update(mid + 1, y, z, p * 2 + 1);
        up(p);
    }
} tree;
int A[M];
int main() {
    int T, cas = 1;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        string str;
        for(int j = 1; j <= n; j++) {
            string s;
            int a;
            scanf("%d", &a); cin >> s;
            while(a--) str += s;
        }
        int m = str.size();
        tree.build(1, m, 1, str);
        printf("Case %d:\n", cas++);
        int q, Q = 1;
        scanf("%d", &q);
        while(q--) {
            char s[2];
            int a, b;
            scanf("%s%d%d", s, &a, &b);
            if(s[0] == 'F') tree.update(a + 1, b + 1, 1, 1);
            if(s[0] == 'E') tree.update(a + 1, b + 1, 2, 1);
            if(s[0] == 'I') tree.update(a + 1, b + 1, 3, 1);
            if(s[0] == 'S') printf("Q%d: %d\n", Q++, tree.query(a + 1, b + 1, 1));
        }
    }
    return 0;
}

高级姿势

对线段树高级姿势有兴趣的同学

戳这里

LCY表示太弱看不懂 有菊苣看懂了教教我