线段树

洛谷 P3372 【模板】线段树 1

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(1e5 + 10);

struct node {
    int l, r;
    ll sum, lz;
} tree[maxn << 2];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int ls(int cur)
{
    return cur << 1;
}

inline int rs(int cur)
{
    return cur << 1 | 1;
}

void push_up(int cur)
{
    tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum;
}

void push_down(int cur)
{
    if (tree[cur].lz) {
        tree[ls(cur)].sum += (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].lz;
        tree[rs(cur)].sum += (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].lz;
        tree[ls(cur)].lz += tree[cur].lz;
        tree[rs(cur)].lz += tree[cur].lz;
        tree[cur].lz = 0;
    }
}

void build(int cur, int l, int r)
{
    tree[cur].l = l;
    tree[cur].r = r;
    tree[cur].lz = 0;
    if (l == r) {
        tree[cur].sum = read();
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(cur), l, mid);
    build(rs(cur), mid + 1, r);
    push_up(cur);
}

void update(int cur, int l, int r, int v)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        tree[cur].sum += (r - l + 1) * v;
        tree[cur].lz += v;
        return;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        update(ls(cur), l, r, v);
    } else if (l > mid) {
        update(rs(cur), l, r, v);
    } else {
        update(ls(cur), l, mid, v);
        update(rs(cur), mid + 1, r, v);
    }
    push_up(cur);
}

ll query(int cur, int l, int r)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        return tree[cur].sum;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) return query(ls(cur), l, r);
    if (l > mid) return query(rs(cur), l, r);
    return query(ls(cur), l, mid) + query(rs(cur), mid + 1, r);
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    int n = read(), m = read();
    build(1, 1, n);
    while (m--) {
        int t = read(), x = read(), y = read();
        if (t == 1) {
            int k = read();
            update(1, x, y, k);
        } else {
            write(query(1, x, y), true);
        }
    }
    return 0;
}

洛谷 P3373 【模板】线段树 2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(1e5 + 10);
int mod;

struct {
    int l, r;
    ll val, add, mult;
} tree[maxn << 2];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int ls(int cur)
{
    return cur << 1;
}

inline int rs(int cur)
{
    return cur << 1 | 1;
}

void push_up(int cur)
{
    tree[cur].val = (tree[ls(cur)].val + tree[rs(cur)].val) % mod;
}

void push_down(int cur)
{
    if (tree[cur].add or tree[cur].mult not_eq 1) {
        tree[ls(cur)].val = ((tree[ls(cur)]).val * tree[cur].mult + (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].add) % mod;
        tree[rs(cur)].val = ((tree[rs(cur)]).val * tree[cur].mult + (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].add) % mod;
        tree[ls(cur)].mult = tree[ls(cur)].mult * tree[cur].mult % mod;
        tree[rs(cur)].mult = tree[rs(cur)].mult * tree[cur].mult % mod;
        tree[ls(cur)].add = (tree[ls(cur)].add * tree[cur].mult + tree[cur].add) % mod;
        tree[rs(cur)].add = (tree[rs(cur)].add * tree[cur].mult + tree[cur].add) % mod;
        tree[cur].add = 0;
        tree[cur].mult = 1;
    }
}

void build(int cur, int l, int r)
{
    tree[cur].l = l;
    tree[cur].r = r;
    tree[cur].mult = 1;
    if (l == r) {
        tree[cur].val = read();
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(cur), l, mid);
    build(rs(cur), mid + 1, r);
    push_up(cur);
}

void update(int cur, int l, int r, int op, int v)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        if (op == 1) {
            tree[cur].val = tree[cur].val * v % mod;
            tree[cur].add = tree[cur].add * v % mod;
            tree[cur].mult = tree[cur].mult * v % mod;
        } else {
            tree[cur].val = (tree[cur].val + (r - l + 1) * v) % mod;
            tree[cur].add = (tree[cur].add + v) % mod;
        }
        return;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        update(ls(cur), l, r, op, v);
    } else if (l > mid) {
        update(rs(cur), l, r, op, v);
    } else {
        update(ls(cur), l, mid, op, v);
        update(rs(cur), mid + 1, r, op, v);
    }
    push_up(cur);
}

ll query(int cur, int l, int r)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        return tree[cur].val;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        return query(ls(cur), l, r);
    }
    if (l > mid) {
        return query(rs(cur), l, r);
    }
    return (query(ls(cur), l, mid) + query(rs(cur), mid + 1, r)) % mod;
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    int n = read(), m = read();
    mod = read();
    build(1, 1, n);
    while (m--) {
        int op = read(), x = read(), y = read();
        if (op == 3) {
            write(query(1, x, y), true);
        } else {
            update(1, x, y, op, read());
        }
    }
    return 0;
}