【題解】CSES 1736 Polynomial Queries

#include <iostream>
using namespace std;
 
int n, q;
long long st[200005 << 2], lazy[200005 << 2], lazy2[200005 << 2];
 
void push(int x, int l, int r, int mid){
    if (!lazy[x]) return;
    st[x<<1] += 1LL*(lazy[x] + lazy[x]+(mid-l)*lazy2[x])*(mid-l+1)/2;
    lazy[x<<1] += lazy[x];
    lazy2[x<<1] += lazy2[x];
    st[x<<1|1] += 1LL*(lazy[x]+(mid+1-l)*lazy2[x] + lazy[x]+(r-l)*lazy2[x])*(r-mid)/2;
    lazy[x<<1|1] += 1LL*(lazy[x]+(mid+1-l)*lazy2[x]);
    lazy2[x<<1|1] += lazy2[x];
    lazy[x] = 0;
    lazy2[x] = 0;
}
void update(int x, int l, int r, int ul, int ur, int u){
    if (ul <= l && r <= ur){
        st[x] += 1LL*(u+(u+r-l))*(r-l+1)/2;
        lazy[x] += u;
        lazy2[x]++;
        return;
    }
    int mid = (l+r) >> 1;
    push(x, l, r, mid);
    if (ul <= mid) update(x<<1, l, mid, ul, ur, u);
    if (mid < ur) update(x<<1|1, mid+1, r, ul, ur, u+max(0, (mid-max(l, ul)+1)));
    st[x] = st[x<<1] + st[x<<1|1];
}
long long query(int x, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr) return st[x];
    int mid = (l+r) >> 1;
    push(x, l, r, mid);
    long long ret = 0;
    if (ql <= mid) ret += query(x<<1, l, mid, ql, qr);
    if (mid < qr) ret += query(x<<1|1, mid+1, r, ql, qr);
    return ret;
}
void build(int x, int l, int r){
    if (l == r){
        cin >> st[x];
        return;
    }
    int mid = (l+r)>>1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    st[x] = st[x<<1]+st[x<<1|1];
}
 
int main() {
    cin >> n >> q;
    build(1, 1, n);
    for (int i = 1, t, a, b; i <= q; i++){
        cin >> t >> a >> b;
        if (t == 1) update(1, 1, n, a, b, 1);
        else cout << query(1, 1, n, a, b) << "\n";
    }
}