洛谷-P3372-线段树1

线段树

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int MAXN = 100010;
struct Node {
    int l, r;
    LL lazy;
    LL sum;
} segTree[MAXN * 4];
void build(int i, int l, int r) {
    segTree[i].l = l;
    segTree[i].r = r;
    if (l == r) {
        scanf("%lld", &segTree[i].sum);
        return;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum;
}
void push_up(int i, LL v) {
    segTree[i].sum += (segTree[i].r - segTree[i].l + 1) * v;
    segTree[i].lazy += v;
}
void push_down(int i) {
    if (segTree[i].l == segTree[i].r) return;
    push_up(i << 1, segTree[i].lazy);
    push_up(i << 1 | 1, segTree[i].lazy);
    segTree[i].lazy = 0;
}
void add(int i, int l, int r, LL v) {
    if (segTree[i].l >= l && segTree[i].r <= r) {
        push_up(i, v);
        return;
    }
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (mid >= l) add(i << 1, l, r, v);
    if (mid < r) add(i << 1 | 1, l, r, v);
    segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum;
}
LL query(int i, int l, int r) {
    if (segTree[i].l == l && segTree[i].r == r) return segTree[i].sum;
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (r <= mid) return query(i << 1, l, r);
    else if (l > mid) return query(i << 1 | 1, l, r);
    else return query(i << 1, l, mid) + query(i << 1 | 1, mid + 1, r);
}
int main() {
    int n, m, op;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    int l, r; LL v;
    while (m--) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d%lld", &l, &r, &v);
            add(1, l, r, v);
        } else {
            scanf("%d%d", &l, &r);
            printf("%lld
", query(1, l, r));
        }
    }
    return 0;
}

洛谷-P3373-线段树2

线段树

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 100010;
struct Node {
    int l, r;
    int val;
    int mul, add;
} segTree[MAXN * 4];
int n, m, p;
void build(int i, int l, int r) {
    segTree[i].l = l; segTree[i].r = r;
    segTree[i].mul = 1; segTree[i].add = 0;
    if (l == r) {
        scanf("%d", &segTree[i].val);
        return;
    } 
    int mid = l + r >> 1;
    build(i << 1, l, mid); build(i << 1 | 1, mid + 1, r);
    segTree[i].val = (segTree[i << 1].val + segTree[i << 1 | 1].val) % p;
}
void push_up(int i, int mul, int add) {
    segTree[i].val = (1LL * segTree[i].val * mul + 1LL * add * (segTree[i].r - segTree[i].l + 1)) % p;
    segTree[i].mul = (1LL * segTree[i].mul * mul) % p;
    segTree[i].add = (1LL * segTree[i].add * mul + add) % p;
}
void push_down(int i) {
    if (segTree[i].l == segTree[i].r) return;
    push_up(i << 1, segTree[i].mul, segTree[i].add);
    push_up(i << 1 | 1, segTree[i].mul, segTree[i].add);
    segTree[i].mul = 1; segTree[i].add = 0;
}
void mul(int i, int l, int r, int k) {
    if (segTree[i].l == l && segTree[i].r == r) {
        push_up(i, k, 0);
        return;
    }
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (r <= mid) {
        mul(i << 1, l, r, k);
    } else if (l > mid) {
        mul(i << 1 | 1, l, r, k);
    } else {
        mul(i << 1, l, mid, k);
        mul(i << 1 | 1, mid + 1, r, k);
    }
    segTree[i].val = (segTree[i << 1].val + segTree[i << 1 | 1].val) % p;
}
void add(int i, int l, int r, int k) {
    if (segTree[i].l == l && segTree[i].r == r) {
        push_up(i, 1, k);
        return;
    }
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (r <= mid) {
        add(i << 1, l, r, k);
    } else if (l > mid) {
        add(i << 1 | 1, l, r, k);
    } else {
        add(i << 1, l, mid, k);
        add(i << 1 | 1, mid + 1, r, k);
    }
    segTree[i].val = (segTree[i << 1].val + segTree[i << 1 | 1].val) % p;
}
int query(int i, int l, int r) {
    if (segTree[i].l == l && segTree[i].r == r) return segTree[i].val;
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (r <= mid) return query(i << 1, l, r);
    else if (l > mid) return query(i << 1 | 1, l, r);
    else return (query(i << 1, l, mid) + query(i << 1 | 1, mid + 1, r)) % p;
}
int main() {
    int op, l, r, k;
    scanf("%d%d%d", &n, &m, &p);
    build(1, 1, n);
    while (m--) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d%d", &l, &r, &k);
            mul(1, l, r, k);
        } else if (op == 2) {
            scanf("%d%d%d", &l, &r, &k);
            add(1, l, r, k);
        } else {
            scanf("%d%d", &l, &r);
            printf("%d
", query(1, l, r));
        }
    }
    return 0;
}