进阶数据结构应用-维护序列

题目-维护序列

问题分析

三个操作

• 区间整体乘一个数字
• 区间整体加一个数字
• 查询区间的和

线段树需要记录的属性

• 节点的左右边界
• $add$, $sum$, 代表加法的延迟标记, 和区间和
• $mul$乘法的延迟标记

但是延迟标记是有更新顺序的, 可以做如下假设, 假设当前考虑的区间是$[l,r]$, 加法标记是$add$, 乘法标记是$mul$

如果对于区间中每个数字先做加法再做加法, 假设区间中某个数字是$x$, 那么有
$$(x+add)\cdot mul$$
此时, 父节点加法延迟标记下传, 假设是$t$, 很难在原数字基础上加$t$, 得到下面的式子(除非$mul$能整除$t$)
$$(x+t+add)\cdot mul$$

但是假设先做乘法再做加法有
$$x\cdot mul+add$$
(1)此时, 父节点加法延迟标记下传, 假设是$t$
$$x\cdot mul+add+t$$
只需要将$add=add+t$, 很容易得到新的$x$
(2)再讨论, 父节点的乘法延迟标记下传, 假设是$c$
$$(x\cdot mul+add)\cdot c$$
只需要将原$mul=mul\cdot c$, $add=add\cdot c$, 就能实现乘法延迟标记更新

因此对于延迟标记的更新, 我们认为的规定先更新乘法延迟标记再更新加法延迟标记

具体的来说假设当前节点的加法延迟标记是$a$, 乘法延迟标记是$b$, 父节点向下传递的加法标记是$c$, 乘法标记是$d$, 那么有

$$(x\cdot b+a)\cdot d+c=x\cdot bd+ad+c$$

那么新的加法延迟标记是$ad+c$, 新的乘法延迟标记是$bd$

算法步骤

• 实现push up操作
• 实现先计算乘法再计算加法的延迟标记更新函数push down
• 实现区间修改操作, 当递归到子区间的时候, 直接调用push down对当前区间进行修改
• 实现区间查询

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, m, p;
int w[N];
struct Node {
   
    int l, r;
    LL sum, add, mul;
} tr[N << 2];

void pushup(int u) {
   
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void pushdown(Node &u, LL add, LL mul) {
   
    u.sum = (u.sum * mul + (u.r - u.l + 1) * add % p) % p;
    u.add = (u.add * mul % p + add) % p;
    u.mul = u.mul * mul % p;
}

void pushdown(int u) {
   
    pushdown(tr[u << 1], tr[u].add, tr[u].mul);
    pushdown(tr[u << 1 | 1], tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r) {
   
    if (l == r) {
   
        tr[u] = {
   l, r, w[l], 0, 1};
        return;
    }
    tr[u] = {
   l, r, 0, 0, 1};
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int ql, int qr, LL add, LL mul) {
   
    if (tr[u].l >= ql && tr[u].r <= qr) {
   
        pushdown(tr[u], add, mul);
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (ql <= mid) modify(u << 1, ql, qr, add, mul);
    if (qr > mid) modify(u << 1 | 1, ql, qr, add, mul);
    pushup(u);
}

LL query(int u, int ql, int qr) {
   
    if (tr[u].l >= ql && tr[u].r <= qr) return tr[u].sum;

    pushdown(u);
    LL ans = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (ql <= mid) ans = (ans + query(u << 1, ql, qr)) % p;
    if (qr > mid) ans = (ans + query(u << 1 | 1, ql, qr)) % p;
    pushup(u);
    return ans;
}


int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> p;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    build(1, 1, n);
    cin >> m;

    while (m--) {
   
        int c;
        cin >> c;
        if (c == 1) {
   
            int l, r, val;
            cin >> l >> r >> val;
            modify(1, l, r, 0, val);
        }
        else if (c == 2) {
   
            int l, r, val;
            cin >> l >> r >> val;
            modify(1, l, r, val, 1);
        }
        else {
   
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r) % p << '\n';
        }
    }
    
    return 0;
}