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

ll a[N], sum[4 * N], tag[4 * N], ans;
struct Node {
    int l, r;
} p[4 * N];

void add(int x, ll k) {
    sum[x] += k * (p[x].r - p[x].l + 1);
    tag[x] += k;
}

void up(int x) { sum[x] = sum[2 * x] + sum[2 * x + 1]; }

void down(int x) {
    if (tag[x]) {
        add(2 * x, tag[x]);
        add(2 * x + 1, tag[x]);
        tag[x] = 0;
    }
}

void build(int x, int l, int r) {
    p[x].l = l;
    p[x].r = r;
    sum[x] = 0;
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    down();
    int mid = (l + r) >> 1;
    if (l <= mid) build(2 * x, l, mid);
    if (r > mid) build(2 * x + 1, mid + 1, r);
    up(x);
}

void ask(int x, int l, int r, int L, int R) {
    if (R < l || L > r) return;
    if (l >= L && r <= R) {
        ans += sum[x];
        return;
    }
    int mid = (l + r) >> 1;
    down(x);
    if (l <= mid) ask(2 * x, l, mid, L, R);
    if (r > mid) ask(2 * x + 1, mid + 1, r, L, R);
    up(x);
}

void insert(int x, int l, int r, int L, int R, int k) {
    if (r < L || l > R) return;
    if (l >= L && r <= R) {
        add(x, k);
        return;
    }
    int mid = (l + r) >> 1;
    down(x);
    if (l <= mid) insert(2 * x, l, mid, L, R, k);
    if (mid < r) insert(2 * x + 1, mid + 1, r, L, R, k);
    up(x);
}

 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

void up(int x) { sum[x] = sum[x << 1] + sum[(x << 1) + 1]; }

void change(int x, int k, int b) {
    mu[x] = 1ll * mu[x] * k % P;
    ad[x] = (1ll * ad[x] * k + b) % P;
    sum[x] = (1ll * sum[x] * k + 1ll * b * (p[x].r - p[x].l + 1)) % P;
}

void down(int x) {
    if (mu[x] != 1 || ad[x]) {
        change(x << 1, mu[x], ad[x]);
        change((x << 1) + 1, mu[x], ad[x]);
        mu[x] = 1;
        ad[x] = 0;
    }
}

void build(int x, int l, int r) {
    p[x].l = l;
    p[x].r = r;
    ad[x] = 0;
    mu[x] = 1;
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    down(x);
    int mid = (l + r) >> 1;
    if (l <= mid) build(x << 1, l, mid);
    if (r > mid) build((x << 1) + 1, mid + 1, r);
    up(x);
}

void insert(int x, int l, int r, int L, int R, int k, int b) {
    if (r < L || l > R) return;
    if (L <= l && r <= R) {
        change(x, k, b);
        return;
    }
    down(x);
    int mid = (l + r) >> 1;
    if (l <= mid) insert(x << 1, l, mid, L, R, k, b);
    if (r > mid) insert((x << 1) + 1, mid + 1, r, L, R, k, b);
    up(x);
}

void query(int x, int l, int r, int L, int R) {
    if (r < L || l > R) return;
    if (L <= l && r <= R) {
        ans = (ans + sum[x]) % P;
        return;
    }
    down(x);
    int mid = (l + r) >> 1;
    if (l <= mid) query(x << 1, l, mid, L, R);
    if (r > mid) query((x << 1) + 1, mid + 1, r, L, R);
    up(x);
}