<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为 $N$ 的数列，不妨设为 $a_1,a_2,…,a_N$。

有如下三种操作形式：

1. 把数列中的一段数全部乘一个值；
2. 把数列中的一段数全部加一个值；
3. 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $P$ 的值。

输入格式

第一行两个整数 $N$ 和 $P$；

第二行含有 $N$ 个非负整数，从左到右依次为 $a_1,a_2,…,a_N$；

第三行有一个整数 $M$，表示操作总数；

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

• 操作 $1$：1 t g c，表示把所有满足 $t \\le i \\le g$ 的 $a_i$ 改为 $a_i \\times c$；
• 操作 $2$：2 t g c，表示把所有满足 $t \\le i \\le g$ 的 $a_i$ 改为 $a_i + c$；
• 操作 $3$：3 t g，询问所有满足 $t \\le i \\le g$ 的 $a_i$ 的和模 $P$ 的值。

同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式

对每个操作 $3$，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

数据范围

$1 \\le N,M \\le 10^5$,
$1 \\le t \\le g \\le N$,
$0 \\le c,a_i \\le 10^9$,
$1 \\le P \\le 10^9$

输入样例：

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

样例解释

初始时数列为 $\\lbrace 1,2,3,4,5,6,7 \\rbrace$；

经过第 $1$ 次操作后，数列为 $\\lbrace 1,10,15,20,25,6,7 \\rbrace$；

对第 $2$ 次操作，和为 $10+15+20=45$，模 $43$ 的结果是 $2$；

经过第 $3$ 次操作后，数列为 $\\lbrace 1,10,24,29,34,15,16 \\rbrace$；

对第 $4$ 次操作，和为 $1+10+24=35$，模 $43$ 的结果是 $35$；

对第 $5$ 次操作，和为 $29+34+15+16=94$，模 $43$ 的结果是 $8$。

思路

这里什么都简单，就难在懒标记：
有一个乘法，还有一个加法，那怎么辨别先乘再加还是先加后乘？
这里我们规定，先乘后加。
那如果加法有标记，乘法又修改了呢？我们可以直接把加法标记直接乘以乘法标记的值，然后再加上加法标记，然后就没有然后了。

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,m,p;
int a[N];
struct segment_tree_node {
    int l,r;
    LL add,tim;
    LL sum;
}tr[4 * N];
inline void push_up (int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}
inline void push_down (int u) {
    auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
    left.sum = (left.sum * root.tim + root.add * (left.r - left.l + 1)) % p;
    right.sum = (right.sum * root.tim + root.add * (right.r - right.l + 1)) % p;
    left.tim = left.tim * root.tim % p;
    right.tim = right.tim * root.tim % p;
    left.add = (left.add * root.tim + root.add) % p;
    right.add = (right.add * root.tim + root.add) % p;
    root.tim = 1,root.add = 0;
}
void build_segment_tree (int u,int l,int r) {
    if (l == r) {
        tr[u] = {l,r,0,1,a[l]};
        return ;
    }
    tr[u] = {l,r,0,1};
    int mid = l + r >> 1;
    build_segment_tree (u << 1,l,mid),build_segment_tree (u << 1 | 1,mid + 1,r);
    push_up (u);
}
void modify (int u,int l,int r,LL tim,LL add) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum = (tr[u].sum * tim + add * (tr[u].r - tr[u].l + 1)) % p;
        tr[u].tim = tr[u].tim * tim % p,tr[u].add = (tr[u].add * tim + add) % p;
        return ;
    }
    push_down (u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify (u << 1,l,r,tim,add);
    if (r >= mid + 1) modify (u << 1 | 1,l,r,tim,add);
    push_up (u);
}
LL query (int u,int l,int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    push_down (u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if (l <= mid) sum += query (u << 1,l,r);
    if (r >= mid + 1) sum += query (u << 1 | 1,l,r);
    return sum % p;
}
int main () {
    cin >> n >> p;
    for (int i = 1;i <= n;i++) cin >> a[i];
    build_segment_tree (1,1,n);
    cin >> m;
    while (m--) {
        int op,l,r;
        cin >> op >> l >> r;
        if (op == 1) {
            LL x;
            cin >> x;
            modify (1,l,r,x,0);
        }
        else if (op == 2) {
            LL x;
            cin >> x;
            modify (1,l,r,1,x);
        }
        else cout << query (1,l,r) << endl;
    }
    return 0;
}