跳转至

线段树

区间求最值

 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
#include <bits/stdc++.h>
#define calm ((a + b) >> 1)
using namespace std;
const int MAXn = 1.8e5 + 9;
int d[MAXn + 9], tx[(MAXn << 2) + 9], tn[(MAXn << 2) + 9];
int n;

void fini(int a, int b, int p) {
    if(a == b) return tx[p] = tn[p] = d[a], void();
    int m = calm;
    fini(a, m, p << 1);
    fini(m + 1, b, p << 1 | 1);
    tx[p] = max(tx[p << 1], tx[p << 1 | 1]);
    tn[p] = min(tn[p << 1], tn[p << 1 | 1]);
}

int fgetmx(int x, int y, int a, int b, int p) {
    if(x <= a && b <= y) return tx[p];
    int m = calm, mx = 0;
    if(x <= m) mx = max(mx, fgetmx(x, y, a, m, p << 1));
    if(m + 1 <= y) mx = max(mx, fgetmx(x, y, m + 1, b, p << 1 | 1));
    return mx;
}

int fgetmn(int x, int y, int a, int b, int p) {
    if(x <= a && b <= y) return tn[p];
    int m = calm, mn = INT_MAX;
    if(x <= m) mn = min(mn, fgetmn(x, y, a, m, p << 1));
    if(m + 1 <= y) mn = min(mn, fgetmn(x, y, m + 1, b, p << 1 | 1));
    return mn;
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]);
    fini(1, n, 1);
    for(int i = 1, l, r; i <= m; i ++) {
        scanf("%d%d", &l, &r);
        printf("%d\n", fgetmx(l, r, 1, n, 1) - fgetmn(l, r, 1, n, 1));
    }
    return 0;
}

区间加 区间求和

 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
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 1e5 + 9;
lli t[4 * MAXn + 9], tag[4 * MAXn + 9], dat[MAXn + 9];
int n;

void ini(int a, int b, int p) {
    if(a == b) {
        t[p] = dat[a];
        return;
    }
    int m = (a + b) >> 1;
    ini(a, m, p * 2);
    ini(m + 1, b, p * 2 + 1);
    t[p] = t[p * 2] + t[p * 2 + 1];
}

void fadd(int x, int y, int a, int b, int p, int v) {
    if(x <= a && b <= y) {
        t[p] += v * (b - a + 1);
        tag[p] += v;
        return;
    }
    int m = (a + b) >> 1;
    if(tag[p]) {
        tag[p * 2] += tag[p];
        tag[p * 2 + 1] += tag[p];
        t[p * 2] += tag[p] * (m - a + 1);
        t[p * 2 + 1] += tag[p] * (b - m);
        tag[p] = 0;
    }
    if(x <= m) fadd(x, y, a, m, p * 2, v);
    if(m+1 <= y) fadd(x, y, m + 1, b, p * 2 + 1, v);
    t[p] = t[p * 2] + t[p * 2 + 1];
}

lli fget(int x, int y, int a, int b, int p) {
    if(x <= a && b <= y)
        return t[p];
    int m = (a + b) >> 1;
    if(tag[p]) {
        t[p * 2] += tag[p] * (m - a + 1);
        t[p * 2 + 1] += tag[p] * (b - m);
        tag[p * 2] += tag[p];
        tag[p * 2 + 1] += tag[p];
        tag[p] = 0;
    }
    lli sum = 0;
    if(x <= m) sum += fget(x, y, a, m, p * 2);
    if(m+1 <= y) sum += fget(x, y, m + 1, b, p * 2 + 1);
    return sum;
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &dat[i]);
    ini(1, n, 1);
    int op;
    for(int iot = 1; iot <= m; iot ++) {
        scanf("%d", &op);
        if(op == 1) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            fadd(x, y, 1, n, 1, v);
        }
        else if(op == 2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%lld\n", fget(x, y, 1, n, 1));
        }
    }
    return 0;
}

区间加 区间乘 区间求和

  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
#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int M = 571373;
const int MAXn = 1e5 + 9;
int ori[MAXn + 9], t[4 * MAXn + 9], atg[4 * MAXn + 9], mtg[4 * MAXn + 9];

void pushup(int p) {
    t[p] = (t[p << 1] + t[p << 1 | 1]) % M;
}

void addtag(int a, int b, int p, int v) {
    // p: 子节点
    (atg[p] += v) %= M;
    (t[p] += v * (b - a + 1) % M) %= M;
}

void multag(int a, int b, int p, int v) {
    // p: 子节点
    v %= M;
    (atg[p] *= v) %= M;
    (mtg[p] *= v) %= M;
    (t[p] *= v) %= M;
}

void pushdown(int a, int b, int p) {
    // p: 当前节点
    int m = (a + b) >> 1;
    multag(a, m, p << 1, mtg[p]);
    multag(m + 1, b, p << 1 | 1, mtg[p]);
    addtag(a, m, p << 1, atg[p]);
    addtag(m + 1, b, p << 1 | 1, atg[p]);
    mtg[p] = 1;
    atg[p] = 0;
}

void fini(int a, int b, int p) {
    if(a == b) {
        t[p] = ori[a] % M;
        return;
    }
    int m = (a + b) >> 1;
    fini(a, m, p * 2);
    fini(m + 1, b, p * 2 + 1);
    pushup(p);
}

void fadd(int x, int y, int a, int b, int p, int v) {
    if(x <= a && b <= y) {
        addtag(a, b, p, v);
        return;
    }
    int m = (a + b) >> 1;
    pushdown(a, b, p);
    if(x <= m) fadd(x, y, a, m, p << 1, v);
    if(m+1 <= y) fadd(x, y, m + 1, b, p << 1 | 1, v);
    pushup(p);
}

void fmul(int x, int y, int a, int b, int p, int v) {
    if(x <= a && b <= y) {
        multag(a, b, p, v);
        return;
    }
    int m = (a + b) >> 1;
    pushdown(a, b, p);
    if(x <= m) fmul(x, y, a, m, p << 1, v);
    if(m+1 <= y) fmul(x, y, m + 1, b, p << 1 | 1, v);
    pushup(p);
}

int fget(int x, int y, int a, int b, int p) {
    if(x <= a && b <= y)
        return t[p];
    pushdown(a, b, p);
    int m = (a + b) >> 1;
    int sum = 0;
    if(x <= m) sum += fget(x, y, a, m, p << 1) % M;
    if(m+1 <= y) sum += fget(x, y, m + 1, b, p << 1 | 1) % M;
    return sum % M;
}

signed main() {
    int n, tms, ia;
    scanf("%lld%lld%lld", &n, &tms, &ia);
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &ori[i]);
    for(int i = 1; i <= 4*MAXn; i ++)
        mtg[i] = 1;
    fini(1, n, 1);
    int op;
    for(int ims = 1; ims <= tms; ims ++) {
        scanf("%lld", &op);
        if(op == 1) {
            int x, y, v;
            scanf("%lld%lld%lld", &x, &y, &v);
            fmul(x, y, 1, n, 1, v);
        }
        else if(op == 2) {
            int x, y, v;
            scanf("%lld%lld%lld", &x, &y, &v);
            fadd(x, y, 1, n, 1, v);

        }
        else if(op == 3) {
            int x, y;
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", fget(x, y, 1, n, 1));
        }
    }
    return 0;
}