题目描述

难度分:$1793$

输入$n(1 \leq n \leq 2 \times 10^5)$、$q(1 \leq q \leq 2 \times 10^5)$和两个长为$n$的数组$a$，$b$，元素范围$[0,10^9]$，下标从$1$开始。

然后输入$q$个询问，格式如下：

1. 1 l r x：把$a[l]$到$a[r]$都增加$x$。
2. 2 l r x：把$b[l]$到$b[r]$都增加$x$。
3. 3 l r：输出$(a[l] \times b[l] + a[l+1] \times b[l+1] + … + a[r] \times b[r]) \% 998244353$。

输入样例$1$

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

输出样例$1$

16
25
84

输入样例$2$

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

输出样例$2$

716070898
151723988

算法

懒标记线段树

如果只有一个序列，很容易想到用线段树来维护序列，接下来我们考虑一下线段树怎么维护两个序列的信息？用$x$维护$a$序列的区间和信息，$y$维护$b$序列的区间和信息。$add\_x$和$add\_y$分别为$a$序列和$b$序列上的懒信息，$s$表示区间信息$\Sigma_{i=l}^{r}a_i \times b_i$。

如果对$a$序列的前三个元素加上$d$，$x$信息正常更新，考虑$s$信息如何变化？它会从$a_1 \times b_1 + a_2 \times b_2 + a_3 \times b_3$变成

$(a_1+d) \times b_1 + (a_2+d) \times b_2 + (a_3+d) \times b_3$
$=a_1 \times b_1 + a_2 \times b_2 + a_3 \times b_3+d \times (b_1+b_2+b_3)$
$=s+d \times y$。

同理，如果对$b$序列的前三个元素加上$d$，$s$信息就会变为$s+d \times x$。这样就可以$O(1)$进行$modify$操作了，合并区间的时候需要合并两个子节点的$x$、$y$、$s$三个信息。

复杂度分析

时间复杂度

简历线段树的时间复杂度为$O(nlog_2n)$。每条询问都需要对线段树进行区间修改和区间查询操作，时间复杂度为$O(log_2n)$，因此查询的总时间复杂度为$O(qlog_2n)$。

综上，整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

除了输入的序列$a$和$b$，算法空间消耗的瓶颈在于线段树，线段树开辟的空间为$4n$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 998244353;
int n, q, a[N], b[N];

class SegmentTree {
public:
    struct Tag {
        int add_x, add_y;
        Tag() {
            add_x = add_y = 0;
        }
    };

    struct Info {
        int l, r, x, y, s;
        Tag lazy;
        Info() {}
        Info(int left, int right, int a, int b) {
            l = left, r = right, x = a % MOD, y = b % MOD;
            s = (LL)x * y % MOD;
        }
    } tr[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            tr[u] = Info(l, r, a[l], b[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(u), l, mid);
        build(rc(u), mid + 1, r);
        pushup(u);
    }

    void modify(int l, int r, int d, int type) {
        modify(1, l, r, d, type);
    }

    Info query(int l, int r) {
        return query(1, l, r);
    }

private:
    int lc(int u) { 
        return u<<1;
    }

    int rc(int u) {
        return u<<1|1;
    }

    void pushup(int u) {
        tr[u] = merge(tr[lc(u)], tr[rc(u)]);
    }

    void pushdown(int u) {
        if(not_null(tr[u].lazy)) {
            down(u);
            clear_lazy(tr[u].lazy);      // 标记下传后要清空
        }
    }

    void modify(int u, int l, int r, int d, int type) {
        if(l <= tr[u].l && tr[u].r <= r) {
            set_val(u, d, type);
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(mid >= l) modify(lc(u), l, r, d, type);
        if(mid < r) modify(rc(u), l, r, d, type);
        pushup(u);
    }

    Info query(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) return tr[u];
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l, info.r = rchild.r;
        info.x = (lchild.x + rchild.x) % MOD;
        info.y = (lchild.y + rchild.y) % MOD;
        info.s = (lchild.s + rchild.s) % MOD;
        return info;
    }

    // modify操作到不能递归时，设置节点的属性值
    void set_val(int u, int d, int type) {
        int len = tr[u].r - tr[u].l + 1;
        if(type == 1) {
            // d加在a上
            tr[u].x = (tr[u].x + (LL)d * len % MOD) % MOD;
            tr[u].lazy.add_x = (tr[u].lazy.add_x + d) % MOD;
            tr[u].s = (tr[u].s + (LL)tr[u].y * d % MOD) % MOD;
        }else {
            // d加在b上
            tr[u].y = (tr[u].y + (LL)d * len % MOD) % MOD;
            tr[u].lazy.add_y = (tr[u].lazy.add_y + d) % MOD;
            tr[u].s = (tr[u].s + (LL)tr[u].x * d % MOD) % MOD;
        }
    }

    // 下传标记的规则
    void down(int u) {
        // 父节点有懒标记时，往下传一层
        if(tr[u].lazy.add_x) {
            set_val(lc(u), tr[u].lazy.add_x, 1);
            set_val(rc(u), tr[u].lazy.add_x, 1);
        }
        if(tr[u].lazy.add_y) {
            set_val(lc(u), tr[u].lazy.add_y, 2);
            set_val(rc(u), tr[u].lazy.add_y, 2);
        }
    }

    // 判断标记是否为空的规则
    bool not_null(Tag& lazy) {
        return lazy.add_x != 0 || lazy.add_y != 0;
    }

    // 清空标记的规则
    void clear_lazy(Tag& lazy) {
        lazy.add_x = lazy.add_y = 0;
    }
};

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    SegmentTree seg;
    seg.build(1, 1, n);
    while(q--) {
        int op, l, r, x;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1 || op == 2) {
            scanf("%d", &x);
            seg.modify(l, r, x, op);
        }else {
            printf("%d\n", seg.query(l, r).s);
        }
    }
    return 0;
}