线段树模板题

此题关键在于 pushdown

考虑加法标记 lt1 和 乘法标记 lt2

考虑到乘法优先级 要 高于 加法优先级

因此在 pushdown 里先 传 lt2 再传 lt1

注意 lt2 传的时候，两个儿子的 lt1 也都要乘上 lt2

code:

#include 
    
     #define int long long using namespace std;const int N = 100005;int n, m, P, a[N], maxid = -1, Ans1[N], Ans2[N], cnt = 0;template 
     
      inline void read(T &t) {    t = 0; T m = 1; char ch = getchar();    while(ch < '0' || ch > '9') { if(ch == '-') m = -1; ch = getchar(); }    while(ch >= '0' && ch <= '9') { t = (t << 3) + (t << 1) + (ch & 15); ch = getchar(); }    t *= m;} struct Stree {    int l, r, sum, lt1, lt2;}tree[N << 4];void pushdown(int rt) {    int l1 = tree[rt].lt1, l2 = tree[rt].lt2;    tree[rt << 1].lt2 *= l2, tree[rt << 1].lt2 %= P;    tree[rt << 1 | 1].lt2 *= l2, tree[rt << 1 | 1].lt2 %= P;    tree[rt << 1].lt1 *= l2, tree[rt << 1].lt1 %= P;    tree[rt << 1 | 1].lt1 *= l2, tree[rt << 1 | 1].lt1 %= P;    tree[rt << 1].sum *= l2, tree[rt << 1].sum %= P;    tree[rt << 1 | 1].sum *= l2, tree[rt << 1 | 1].sum %= P;    tree[rt].lt2 = 1;    tree[rt << 1].lt1 += l1, tree[rt << 1].lt1 %= P;    tree[rt << 1 | 1].lt1 += l1, tree[rt << 1 | 1].lt1 %= P;    tree[rt << 1].sum += (tree[rt << 1].r - tree[rt << 1].l + 1) * l1, tree[rt << 1].sum %= P;    tree[rt << 1 | 1].sum += (tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1) * l1, tree[rt << 1 | 1].sum %= P;    tree[rt].lt1 = 0;    }// Checkedvoid pushup(int rt) {    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; tree[rt].sum %= P;}// Checkedvoid build(int l, int r, int rt) {    tree[rt].l = l, tree[rt].r = r, tree[rt].lt1 = 0, tree[rt].lt2 = 1;    if(l == r) { tree[rt].sum = a[l]; tree[rt].sum %= P; return; }    int mid = (l + r) >> 1;    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);    pushup(rt); }int Quary(int L, int R, int l, int r, int rt) {    if(L <= l && r <= R) return tree[rt].sum;    if(tree[rt].lt1 != 0 || tree[rt].lt2 != 1) pushdown(rt);    int ans = 0, mid = (l + r) >> 1;    if(L <= mid) ans += Quary(L, R, l, mid, rt << 1);    if(R > mid) ans += Quary(L, R, mid + 1, r, rt << 1 | 1);     return ans;} void upd1(int L, int R, int C, int l, int r, int rt) {    if(L <= l && r <= R) {        tree[rt].sum += (r - l + 1) * C; tree[rt].sum %= P;        tree[rt].lt1 += C; tree[rt].lt1 %= P; return;    }    if(tree[rt].lt1 != 0 || tree[rt].lt2 != 1) pushdown(rt);    int mid = (l + r) >> 1;    if(L <= mid) upd1(L, R, C, l, mid, rt << 1);    if(R > mid) upd1(L, R, C, mid + 1, r, rt << 1 | 1);    pushup(rt); }void upd2(int L, int R, int C, int l, int r, int rt) {    if(L <= l && r <= R) {        tree[rt].sum *= C; tree[rt].sum %= P;        tree[rt].lt1 *= C; tree[rt].lt1 %= P;        tree[rt].lt2 *= C; tree[rt].lt2 %= P; return;    }    if(tree[rt].lt1 != 0 || tree[rt].lt2 != 1) pushdown(rt);    int mid = (l + r) >> 1;    if(L <= mid) upd2(L, R, C, l, mid, rt << 1);    if(R > mid) upd2(L, R, C, mid + 1, r, rt << 1 | 1);    pushup(rt);}signed main() {    read(n), read(P);    for(int i = 1; i <= n; i++) {        read(a[i]);    }    build(1, n, 1);    read(m);    for(int i = 1; i <= m; i++) {        int opt; read(opt);        if(opt == 1) {            int x, y, z; read(x), read(y), read(z);            upd2(x, y, z, 1, n, 1);        }        if(opt == 2) {            int x, y, z; read(x), read(y), read(z);            upd1(x, y, z, 1, n, 1);        }        if(opt == 3) {            int x, y; read(x), read(y);            printf("%lld\n", Quary(x, y, 1, n, 1) % P);        }    }    return 0;}