P2023 [AHOI2009]维护序列

线段树模板题

此题关键在于 pushdown

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

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

因此在 pushdown 里先 传 lt2 再传 lt1

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

code:

#include <bits/stdc++.h>
#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 <typename T>
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;	 
}

// Checked
void pushup(int rt) {
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; tree[rt].sum %= P;
}

// Checked
void 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
", Quary(x, y, 1, n, 1) % P);
        }
    }
    return 0;
}