1277 维护序列（线段树）

水深无声 2022-09-09 00:28 151阅读 0赞

**1. 问题描述：**

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。有长为 N 的数列，不妨设为 a1，a2，…，aN。  
有如下三种操作形式：  
把数列中的一段数全部乘一个值；  
把数列中的一段数全部加一个值；  
询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。

**输入格式**

第一行两个整数 N 和 P；  
第二行含有 N 个非负整数，从左到右依次为 a1，a2，…，aN；  
第三行有一个整数 M，表示操作总数；  
从第四行开始每行描述一个操作，输入的操作有以下三种形式：  
操作 1：1 t g c，表示把所有满足 t ≤ i ≤ g 的 ai 改为 ai × c；  
操作 2：2 t g c，表示把所有满足 t ≤ i ≤ g 的 ai 改为 ai + c；  
操作 3：3 t g，询问所有满足 t≤i≤g 的 ai 的和模 P 的值。  
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

**输出格式**

对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。  
数据范围  
1 ≤ N，M ≤ 10 ^ 5，  
1 ≤ t ≤ g ≤ N,  
0 ≤ c，ai ≤ 109,  
1 ≤ P ≤ 109

**输入样例：**

7 43  
1 2 3 4 5 6 7  
5  
1 2 5 5  
3 2 4  
2 3 7 9  
3 1 3  
3 4 7

**输出样例：**  
2  
35  
8  
样例解释  
初始时数列为 \{1，2，3，4，5，6，7\}；  
经过第 1 次操作后，数列为 \{1，10，15，20，25，6，7\}；  
对第 2 次操作，和为 10+15+20=45，模 43 的结果是 2；  
经过第 3 次操作后，数列为 \{1，10，24，29，34，15，16\}；  
对第 4 次操作，和为 1+10+24=35，模 43 的结果是 35；  
对第 5 次操作，和为 29+34+15+16=94，模 43 的结果是 8。

来源：[https://www.acwing.com/problem/content/description/1279/][https_www.acwing.com_problem_content_description_1279]

**2. 思路分析：**

分析题目可以知道涉及到**区间修改**与**区间查询**操作，对于这种区间动态修改的问题我们一般是考虑**线段树**来解决，并且这道题目的相关操作没有什么特点（不能够转换为差分思路解决）所以我们不能够转化为没有懒标记的线段树来解决，我们需要使用带有懒标记的线段树来解决。这道题目与之前的题目不一样的是这道题目涉及到区间的乘法和加法，所以会比较复杂一点，对于区间的加法我们可以使用懒标记add来维护，类似地对于区间乘法我们可以使用另外一个懒标记mul来维护。因为存在加法add和乘法mul两个懒标记所以我们需要考虑怎么样运算才能够比较正确与方便计算出当前区间的区间和，可以发现对于当前区间的两个懒标记先乘后加的操作更容易维护，并且我们对于区间加法和乘法不同的操作维护成统一的形式，也即将区间和先乘一个数然后再加一个数：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

根据上面的公式无论是区间加法还是乘法都可以转换为先乘后加的操作，这样就可以更新对应的懒标记即可，对于区间加法，我们可以令c = 1，对于区间乘法可以令d = 0。因为多了一个乘法的懒标记所以使用pushdown操作更新的时候按照上面的式子依次更新加法和乘法的懒标记即可，其余的操作都是与之前只有一个加法懒标记的操作是一样的。

**3. 代码如下：**

**c++：**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    typedef long long LL;
    const int N = 100010;
    int n, p, m;
    int w[N];
    struct Node
    {
        int l, r;
        int sum, add, mul;
    }tr[N * 4];
    
    void pushup(int u)
    {
        tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
    }
    
    void eval(Node &t, int add, int mul)
    {
        t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
        t.mul = (LL)t.mul * mul % p;
        t.add = ((LL)t.add * mul + add) % p;
    }
    
    void pushdown(int u)
    {
        eval(tr[u << 1], tr[u].add, tr[u].mul);
        eval(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[r], 0, 1};
        else
        {
            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 l, int r, int add, int mul)
    {
        if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
        else
        {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) modify(u << 1, l, r, add, mul);
            if (r > mid) modify(u << 1 | 1, l, r, add, mul);
            pushup(u);
        }
    }
    
    int query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int sum = 0;
        if (l <= mid) sum = query(u << 1, l, r);
        if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
        return sum;
    }
    
    int main()
    {
        scanf("%d%d", &n, &p);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
        build(1, 1, n);
    
        scanf("%d", &m);
        while (m -- )
        {
            int t, l, r, d;
            scanf("%d%d%d", &t, &l, &r);
            if (t == 1)
            {
                scanf("%d", &d);
                modify(1, l, r, 0, d);
            }
            else if (t == 2)
            {
                scanf("%d", &d);
                modify(1, l, r, d, 1);
            }
            else printf("%d\n", query(1, l, r));
        }
    
        return 0;
    }

**java：**一开始的时候由于声明的是对象数组所以初始化对象数组的时候消耗了时间所以不能够通过所有的测试用例，后面将对象数组修改为了三个int类型数组的形式才通过了，这样不用初始化对象数组可以减少一定的耗时，本质上是一样的。在使用pushdown更新的时候也是根据图片中的式子来更新的。

import java.util.Scanner;
    public class Main {
        static int []w;
        // sum为区间和数组
        static long []sum;
        // add为和的懒标记数组
        static long []add;
        // mul为乘的懒标记数组
        static long []mul;
        static int p;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            p = sc.nextInt();
            w = new int[n + 1];
            for (int i = 1; i <= n; ++i){
                w[i] = sc.nextInt();
            }
            int m = sc.nextInt();
            sum = new long[4 * n];
            add = new long[4 * n];
            mul = new long[4 * n];
            build(1, 1, n);
            for (int i = 0; i < m; ++i){
                int a, l, r, v;
                a = sc.nextInt();
                l = sc.nextInt();
                r = sc.nextInt();
                // a=3为查询
                if (a == 3){
                    long res = query(1, 1, n, l, r);
                    System.out.println(res);
                }else {
                    v = sc.nextInt();
                    modify(1, 1, n, l, r, v, a);
                }
            }
        }
    
        public static void pushup(int u){
            sum[u] = (sum[u << 1] + sum[u << 1 | 1]) % p;
        }
    
        public static void pushdown(int u, int l, int mid, int r){
            if (add[u] == 0 && mul[u] == 1) return;
            // 更新左边区间的区间和
            sum[u << 1] = (sum[u << 1] * mul[u] + add[u] * (mid - l + 1)) % p;
            // 更新右边区间的区间和
            sum[u << 1 | 1] = (sum[u << 1 | 1] * mul[u] + add[u] * (r - mid)) % p;
            // 更新加法和乘法的懒标记(根据图片中的式子进行更新)
            add[u << 1] = (add[u] + add[u << 1] * mul[u]) % p;
            add[u << 1 | 1] = (add[u] + add[u << 1 | 1] * mul[u]) % p;
            mul[u << 1] = (mul[u << 1] * mul[u]) % p;
            mul[u << 1 | 1] = (mul[u << 1 | 1] * mul[u]) % p;
            add[u] = 0;
            mul[u] = 1;
        }
    
        public static void build(int u, int l, int r){
            mul[u] = 1;
            if (l == r) {
                sum[u] = w[l];
                return;
            }
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    
        public static void modify(int u, int _l, int _r, int l, int r, int v, int op){
            if (_l >= l && _r <= r){
                if (op == 1){
                    // 整个区间乘以一个数根据图片中的公式进行更新
                    sum[u] = (sum[u] * v) % p;
                    add[u] = (add[u] * v) % p;
                    mul[u] = (mul[u] * v) % p;
                }else {
                    sum[u] = (sum[u] + (_r - _l + 1) * v) % p;
                    add[u] = (add[u] + v) % p;
                }
                return;
            }
            int mid = _l + _r >> 1;
            pushdown(u, _l, mid, _r);
            if (l <= mid) modify(u << 1, _l, mid, l, r, v, op);
            if (r > mid) modify(u << 1 | 1, mid + 1, _r, l, r, v, op);
            pushup(u);
        }
    
        public static long query(int u, int _l, int _r, int l, int r){
            if (_l >= l && _r <= r) return sum[u];
            long res = 0;
            int mid = _l + _r >> 1;
            pushdown(u, _l, mid, _r);
            if (l <= mid) res = query(u << 1, _l, mid, l, r) % p;
            if (r > mid) res = (res + query(u << 1 | 1, mid + 1, _r, l, r)) % p;
            return res;
        }
    }

**超时：**

import java.util.Scanner;
    public class Main {
        static Tree []tree;
        static int []w;
        static int p;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            p = sc.nextInt();
            w = new int[n + 1];
            for (int i = 1; i <= n; ++i){
                w[i] = sc.nextInt();
            }
            int m = sc.nextInt();
            tree = new Tree[4 * n];
            // 新建每一个线段树节点
            for (int i = 0; i < 4 * n; ++i){
                tree[i] = new Tree();
            }
            build(1, 1, n);
            for (int i = 0; i < m; ++i){
                int a, l, r, v;
                a = sc.nextInt();
                l = sc.nextInt();
                r = sc.nextInt();
                // a=3为查询
                if (a == 3){
                    long res = query(1, l, r);
                    System.out.println(res);
                }else if (a == 2){
                    // a=2为区间加上一个数字
                    v = sc.nextInt();
                    modify(1, l, r, v, 1);
                }else {
                    v = sc.nextInt();
                    modify(1, l, r, 0, v);
                }
            }
        }
    
        // 由子区间的区间和计算父节点的区间和
        public static void pushup(int u){
            tree[u].sum = (tree[u << 1].sum + tree[u << 1 | 1].sum) % p;
        }
    
        // add和mul为父节点的线段树懒标记
        public static void eval(Tree u, long add, long mul){
            // 更新当前节点的区间和, 加法和乘法的懒标记, , 懒标记更新操作依赖于下加后乘的那个式子
            u.sum = ((u.sum * mul) + (u.r - u.l + 1) * add) % p;
            u.mul = (u.mul * mul) % p;
            u.add = (u.add * mul + add) % p;
        }
    
        public static void pushdown(int u){
            // 将父节点的加和乘的懒标记下传
            eval(tree[u << 1], tree[u].add, tree[u].mul);
            eval(tree[u << 1 | 1], tree[u].add, tree[u].mul);
            tree[u].add = 0;
            tree[u].mul = 1;
        }
    
        public static void build(int u, int l, int r){
            tree[u].l = l;
            tree[u].r = r;
            // 新建线段树节点的时候应该令当前区间的加法懒标记为0, 乘法懒标记为1
            tree[u].add = 0;
            tree[u].mul = 1;
            if (l == r) {
                tree[u].sum = w[l];
                return;
            }
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            // 计算区间和
            pushup(u);
        }
    
        public static void modify(int u, int l, int r, int add, int mul){
            if (tree[u].l >= l && tree[u].r <= r){
                eval(tree[u], add, mul);
                return;
            }
            // 将懒标记下传
            pushdown(u);
            int mid = tree[u].l + tree[u].r >> 1;
            if (l <= mid) modify(u << 1, l, r, add, mul);
            if (r > mid) modify(u << 1 | 1, l, r, add, mul);
            pushup(u);
        }
    
        public static long query(int u, int l, int r){
            if (tree[u].l >= l && tree[u].r <= r) return tree[u].sum;
            pushdown(u);
            long res = 0;
            int mid = tree[u].l + tree[u].r >> 1;
            if (l <= mid) res = query(u << 1, l, r);
            if (r > mid) res = (res + query(u << 1 | 1, l, r)) % p;
            return res;
        }
    
        public static class Tree{
            int l, r;
            long sum;
            // add为区间加的懒标记, mul为区间乘的懒标记
            long add, mul;
        }
    }

[https_www.acwing.com_problem_content_description_1279]: https://www.acwing.com/problem/content/description/1279/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/baf71d3ddeca4692b5e6b7c26e4affa6.png