题目描述

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

有长为 N 的数列，不妨设为 a1,a2,…,aN。

有如下三种操作形式：

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

样例

INPUT
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
OUTPUT
2
35
8

算法1

(模拟) $O(区间长度)$

不用说了吧，直接模拟乘法、加法、查询，复杂度惊人QWQ。

C++ 代码

咕咕咕

算法2

(线段树) $O(log区间长度)$

前置芝士：线段树

想必想切这道题的大佬都珂以爆切线段树模板了吧QWQ

这道题关键点在于线段树中的$lazytag$，注意该题需要让乘法优先级更高，因为如果先加会出现一些分数，分数带来的严重问题就是精度的缺失。所以这道题需要先乘后加。

下面是实现方法：
加法$lazytag$：与正常的线段树一样。
乘法$lazytag$：将原先的加法$lazytag$乘上需要乘的数，在将乘法$lazytag$乘上需要乘的数。下发$lazytag$时记得先下发乘法标记。

之后就是一些细节，比如说乘法$lazytag$初始值为0，标记的值需要模P等。

参考文献

关于线段树的介绍以及一些线段树的运用题。

C++ 代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL tag[400001], a[400001], num[400001], multag[400001];
LL P;

LL lc(LL p){
    return p << 1;
}

LL rc(LL p){
    return p << 1 | 1;
}

void pushup(LL p){
    num[p] = num[lc(p)] + num[rc(p)];
    num[p] %= P;
}

void build(LL p, LL l, LL r){
    multag[p] = 1;
    if (l == r){
        num[p] = a[l];
        num[p] %= P;
        return;
    }
    LL mid = (l + r) >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    pushup(p);
}

void mulupd(LL p, LL l, LL r, LL x){
    multag[p] *= x;
    tag[p] *= x;
    num[p] *= x;
    num[p] %= P;
    multag[p] %= P;
    tag[p] %= P;
}

void upd(LL p, LL l, LL r, LL x){
    tag[p] += x;
    num[p] += (r - l + 1) * x;
    num[p] %= P;
    tag[p] %= P;
}

void pushdown(LL p, LL l, LL r){
    LL mid = (l + r) >> 1;
    mulupd(lc(p), l, mid, multag[p]);
    mulupd(rc(p), mid + 1, r, multag[p]);
    upd(lc(p), l, mid, tag[p]);
    upd(rc(p), mid + 1, r, tag[p]);
    multag[p] = 1;
    tag[p] = 0;
}

void change(LL L, LL R, LL l, LL r, LL p, LL x){
    if (L <= l && r <= R){
        tag[p] += x;
        num[p] += (r - l + 1) * x;
        num[p] %= P;
        tag[p] %= P;
        return;
    }
    pushdown(p, l, r);
    LL mid = (l + r) >> 1;
    if (L <= mid) change(L, R, l, mid, lc(p), x);
    if (R >= mid + 1) change(L, R, mid + 1, r, rc(p), x);
    pushup(p);
}

void mulchange(LL L, LL R, LL l, LL r, LL p, LL x){
    if (L <= l && r <= R){
        tag[p] *= x;
        multag[p] *= x;
        num[p] *= x;
        num[p] %= P;
        multag[p] %= P;
        tag[p] %= P;
        return;
    }
    pushdown(p, l, r);
    LL mid = (l + r) >> 1;
    if (L <= mid) mulchange(L, R, l, mid, lc(p), x);
    if (R >= mid + 1) mulchange(L, R, mid + 1, r, rc(p), x);
    pushup(p);
}

LL Q(LL L, LL R, LL l, LL r, LL p){
    if (L <= l && r <= R){
        return num[p] % P;
    }
    LL ans = 0;
    pushdown(p, l, r);
    LL mid = (l + r) >> 1;
    if (L <= mid) ans += Q(L, R, l, mid, lc(p));
    ans %= P;
    if (R >= mid + 1) ans += Q(L, R, mid + 1, r, rc(p));
    ans %= P;
    return ans;
}

int main(){
    LL n, m;
    cin >> n >> P;
    for (LL i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    cin >> m; 
    build(1, 1, n);
    for (LL i = 1; i <= m; i++){
        LL type;
        scanf("%lld", &type);
        if (type == 1){
            LL l, r, x;
            scanf("%lld%lld%lld", &l, &r, &x);
            mulchange(l, r, 1, n, 1, x);
        }
        else if (type == 2){
            LL l, r, x;
            scanf("%lld%lld%lld", &l, &r, &x);
            change(l, r, 1, n, 1, x);
        }
        else{
            LL l, r;
            scanf("%lld%lld", &l, &r);
            printf("%lld\n", Q(l, r, 1, n, 1) % P);
        }
    }
    return 0;
}