题解 | #数据结构#

题目数据太水了也，pushdown写错也能过，pushdown按理来说应该先乘后加的，没想到先加后乘居然也能过，贴一组样例

他人提交里面的代码慎用，有些连我这组样例都过不去，不要拿过来就用

5 6
1 2 3 4 5
1 1 5
2 1 5
3 1 5 2
4 1 5 2
1 1 4
2 2 3

先加后乘算出来是

15
55
40
596

这明显是错的 正确结果应该是先乘后加

15
55
28
100

本题的难点就在于pushdown

结构体

#include <iostream>

#define ls u << 1
#define rs u << 1 | 1

using namespace std;

const int N = 10010;
typedef long long LL;
int n, m, a[N];
struct Node
{
    int l, r;
    LL sum1, sum2;//区间和   区间平方和
    LL mul, add;
}tr[N << 2];

template<class T>
inline void read(T &res)
{
    char ch; bool flag = false;
    while ((ch = getchar()) < '0' || ch > '9')
        if (ch == '-') flag = true;
    res = (ch ^ 48);
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = (res << 1) + (res << 3) + (ch ^48);
    if (flag) res = ~res + 1;
}

void pushup(int u) 
{
    tr[u].sum1 = tr[ls].sum1 + tr[rs].sum1;
    tr[u].sum2 = tr[ls].sum2 + tr[rs].sum2;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0, 1, 0};
    if (l == r)
    {
        tr[u].sum1 = a[l], tr[u].sum2 = a[l] * a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

void change(int u, LL mul, LL add)
{
    tr[u].sum2 = mul * mul * tr[u].sum2 + 2 * mul * add * tr[u].sum1 + (tr[u].r - tr[u].l + 1) * add * add;
    tr[u].sum1 = mul * tr[u].sum1 + (tr[u].r - tr[u].l + 1) * add;
    tr[u].mul *= mul, tr[u].add = tr[u].add * mul + add;
}

void pushdown(int u)
{
    change(ls, tr[u].mul, tr[u].add), change(rs, tr[u].mul, tr[u].add);
    tr[u].mul = 1, tr[u].add = 0;
}

void modify(int u, int x, int y, LL mul, LL add)
{
    if (x <= tr[u].l && tr[u].r <= y) {change(u, mul, add); return ;}
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(ls, x, y, mul, add);
    if (y > mid) modify(rs, x, y, mul, add);
    pushup(u);
}

LL query(int u, int x, int y, int op)
{
    if (x <= tr[u].l && tr[u].r <= y)
    {
        if (op == 1) return tr[u].sum1;
        else return tr[u].sum2;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if (x <= mid) res += query(ls, x, y, op);
    if (y > mid) res += query(rs, x, y, op);\
    return res;
}

int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; i ++) read(a[i]);
    build(1, 1, n);

    while (m --)
    {
        int op, x, y, v;
        read(op), read(x), read(y);
        if (op == 1 || op == 2) printf("%lld\n", query(1, x, y, op));
        else if (op == 3) read(v), modify(1, x, y, v, 0);
        else read(v), modify(1, x, y, 1, v);
    }

    return 0;
}