【題解】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";
}
}
```