萌新 xds 模板 WA on 后 3 点求调

#include <iostream>
using namespace std;

typedef long long ll;

constexpr int MAXN = 1e5 + 5;
constexpr int mod = 571373;

int n;
ll tree[MAXN << 2], tag[MAXN << 2], tag2[MAXN << 2];
int a[MAXN];

inline int ls(int x) {return (x << 1);}
inline int rs(int x) {return (x << 1 | 1);}
inline int mid(int l, int r) {return l + ((r - l) >> 1);}
inline void push_up(int u) {tree[u] = (tree[ls(u)] + tree[rs(u)]) % mod;}

inline void change(int l, int r, int add, int mul, int u) {
    tree[u] = (mul * tree[u] % mod + (r - l + 1) * add % mod) % mod;
    (tag2[u] *= mul) %= mod, tag[u] = (add + mul * tag[u] % mod) % mod;
}

inline void push_down(int l, int r, int u) {
    change(l, mid(l, r), tag[u], tag2[u], ls(u)), change(mid(l, r) + 1, r, tag[u], tag2[u], rs(u));
    tag[u] = 0, tag2[u] = 1;
}

inline void build(int l, int r, int u) {
    tag[u] = 0, tag2[u] = 1;
    if (l == r) {
        tree[u] = a[r];
        return ;
    }
    build(l, mid(l, r), ls(u)), build(mid(l, r) + 1, r, rs(u));
    push_up(u);
}

inline void upd(int L, int R, int l, int r, int u, int d) {
    if (L <= l && r <= R) {
        (tree[u] += (r - l + 1) * d) %= mod, (tag[u] += d) %= mod;
        return ;
    }
    push_down(l, r, u);
    if (L <= mid(l, r)) upd(L, R, l, mid(l, r), ls(u), d);
    if (R > mid(l, r)) upd(L, R, mid(l, r) + 1, r, rs(u), d);
    push_up(u);
}

inline void upd2(int L, int R, int l, int r, int u, int d) {
    if (L <= l && r <= R) {
        (tree[u] *= d) %= mod, (tag[u] *= d) %= mod, (tag2[u] *= d) %= mod;
        return ;
    }
    push_down(l, r, u);
    if (L <= mid(l, r)) upd2(L, R, l, mid(l, r), ls(u), d);
    if (R > mid(l, r)) upd2(L, R, mid(l, r) + 1, r, rs(u), d);
    push_up(u);
}

inline ll get(int L, int R, int l, int r, int u) {
    if (L <= l && r <= R) return tree[u];
    push_down(l, r, u);
    ll res = 0;
    if (L <= mid(l, r)) res += get(L, R, l, mid(l, r), ls(u));
    if (R > mid(l, r)) res += get(L, R, mid(l, r) + 1, r, rs(u));
    return res % mod;
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, _m;
    cin >> n >> m >> _m;
    for (register int i = 1; i <= n; ++i) cin >> a[i];
    build(1, n, 1);
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            upd2(l, r, 1, n, 1, k);
        } else if (op == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            upd(l, r, 1, n, 1, k);
        } else {
            int l, r;
            cin >> l >> r;
            cout << get(l, r, 1, n, 1) << '\n';
        }
    }
    return 0;
}