线段树离线操作

众所周知，这就是一道很裸的模板题，洛谷模板题
实现功能

• 区间加
• 区间乘
• 区间查询
• 区间覆盖
• 动态增加点

建议结合代码理解

1. 其中动态加点实现起来比较简单，离线一下，先把所有点都加入到数组里，然后再建立一棵线段树。那么数组大小就需要翻倍一下，因为原数据是1e5,操作1e5,不排除全部都是加点操作。
2. 区间加操作和区间乘操作也很简单，mul标记，add标记,sum值。子树add的继承是子树的add乘父亲的mul加上父亲的add。子树的sum就是子树的sum 乘父亲的mul加上子树大小乘父亲add

   void pushdown(int p){//更新这个点下面的
    sum(rson(p)) = (sum(rson(p)) * mul(p) % mod + add(p) * (r(rson(p)) - l(rson(p)) + 1) % mod) % mod;
    sum(lson(p)) = (sum(lson(p)) * mul(p) % mod + add(p) * (r(lson(p)) - l(lson(p)) + 1) % mod) % mod;
    mul(rson(p)) = mul(rson(p)) * mul(p) % mod;
    mul(lson(p)) = mul(lson(p)) * mul(p) % mod;
    add(rson(p)) = (add(rson(p)) * mul(p) % mod + add(p)) % mod;
    add(lson(p)) = (add(lson(p)) * mul(p) % mod + add(p)) % mod;
    add(p) = 0;
    mul(p) = 1;
   }

3. 区间覆盖，有了区间加和区间乘就可以实现了，直接把这一段区间先乘0，在加覆盖值就行了

我用结构体写的，纯模板，有爱自取

#include <cstdio>
#include <iostream>
#define ll long long
const int N = 2e5 + 5;
using namespace std;
ll a[N], mod;
struct node{
    int l,r;
    ll sum, add, mul;
    #define lson(p) p << 1
    #define rson(p) p << 1 | 1
    #define l(p) tree[p].l
    #define r(p) tree[p].r
    #define sum(p) tree[p].sum
    #define add(p) tree[p].add
    #define mul(p) tree[p].mul
}tree[N << 2];
void pushup(int p){//更新这个点
    sum(p) = (sum(lson(p)) + sum(rson(p))) % mod;
}
void pushdown(int p){//更新这个点下面的
    sum(rson(p)) = (sum(rson(p)) * mul(p) % mod + add(p) * (r(rson(p)) - l(rson(p)) + 1) % mod) % mod;
    sum(lson(p)) = (sum(lson(p)) * mul(p) % mod + add(p) * (r(lson(p)) - l(lson(p)) + 1) % mod) % mod;
    mul(rson(p)) = mul(rson(p)) * mul(p) % mod;
    mul(lson(p)) = mul(lson(p)) * mul(p) % mod;
    add(rson(p)) = (add(rson(p)) * mul(p) % mod + add(p)) % mod;
    add(lson(p)) = (add(lson(p)) * mul(p) % mod + add(p)) % mod;
    add(p) = 0;
    mul(p) = 1;
}
void bulid(int p, int l, int r){
    l(p) = l,r(p) = r,mul(p) = 1;
    if(r == l){
        sum(p) = a[l] % mod;
        return;
    }
    int mid = (l + r) >> 1;
    bulid(lson(p),l,mid);
    bulid(rson(p),mid+1,r);
    pushup(p);
}
void ChangeAdd(int p, int l, int r, int c){//[l,r]区间加c
    if(l <= l(p) && r(p) <= r){
        sum(p) = (sum(p) + (ll)(r(p) - l(p) + 1) * c % mod) % mod;
        add(p) = (add(p) + c) % mod;
        return;
    }
    pushdown(p);
    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid)ChangeAdd(lson(p), l, r, c);
    if(r > mid)ChangeAdd(rson(p), l, r, c);
    pushup(p);
}
void ChangeMull(int p, int l, int r, int c){//[l,r]区间乘c
    if(l <= l(p) && r(p) <= r){
        mul(p) = mul(p) * c % mod;
        sum(p) = sum(p) * c % mod;
        add(p) = add(p) * c % mod;
        return;
    }
    pushdown(p);
    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid)ChangeMull(lson(p), l, r, c);
    if(r > mid)ChangeMull(rson(p), l, r, c);
    pushup(p);
}
void Change(int p, int l, int r, int c){
    ChangeMull(1, l, r, 0);
    ChangeAdd(1, l, r, c);
}
ll Query(int p, int l, int r){//[l,r]的和
    if(l <= l(p) && r(p) <= r)return sum(p);
    pushdown(p);
    int mid = (l(p) + r(p)) >> 1;
    ll ans = 0;
    if(l <= mid)ans = (ans + Query(lson(p),l,r)) % mod;
    if(r > mid)ans = (ans + Query(rson(p),l,r)) % mod;
    return ans % mod;
}
struct Operation{
    int op, l, r, k;
}O[N];
int main(){
    int n, m, op;
    scanf("%d%d%lld", &n, &m, &mod);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int i = 1; i <= m; i++){
        scanf("%d", &op);
        if(op == 4){
            scanf("%lld",&a[++n]);
        }else{
            int l, r, k = 0;
            scanf("%d%d", &l, &r);
            if(op != 5)scanf("%d", &k);
            O[i].op = op, O[i].l = l;
            O[i].r = r, O[i].k = k;
        }
    }
    bulid(1, 1, n);
    for(int i = 1; i <= m; i++){
        if(O[i].op == 1)ChangeAdd(1, O[i].l, O[i].r, O[i].k);
        else if(O[i].op == 2)ChangeMull(1, O[i].l, O[i].r, O[i].k);
        else if(O[i].op == 3)Change(1, O[i].l, O[i].r, O[i].k);
        else if(O[i].op == 5)printf("%lld\n",Query(1, O[i].l, O[i].r) );
    }
}