題意

給定一個序列$A=(A_1,A_2,?,A_n)$。
現在進行$m$次操作，分為以下兩種:

• 1 l r k d：給定一個長度為$r?l+1$的等差序列，首項為$k$，公差為$d$，并將它對應加到 $[l,r]$范圍中的每一個數上。
• 2 x：查詢$A_x$的值。

思路

將序列$A$進行差分，記差分數組為$B$。
接下來，如果要加上一個等差序列，則要進行以下操作：

• $B_l=B_l+k$
• $B_i=B_i+d(i\in [l,r])$
• $B_{r+1}=B_{r+1}?(k+d\times (r?l))$

如果不懂，看看下面的例子：
原序列：?$A=(0,0,0,0,0,0)$
差分序列：$B=(0,0,0,0,0,0)$
等差序列：$C=(1,3,5,7,9)$
現序列：?$A=(1,3,5,7,9,0)$
差分序列：$B=(1,2,2,2,2,?9)$

如果要查詢$A_p$，就輸出${\sum }_{i=1}^p{B}_i$。
執行以上操作，只需要一個支持單點修改、區間修改。區間查詢的線段樹即可。

代碼

#include <iostream>
#include <vector>
using namespace std;#define int long longstruct segment{#define ls (u << 1)#define rs (u << 1 | 1)struct Node{int l, r, sum = 0, add = 0;};vector<Node> tr;segment(vector<int> &a){int n = a.size();tr.resize(n << 2);build(1, 1, n, a);}void pushup(int u){tr[u].sum = tr[ls].sum + tr[rs].sum;;}void build(int u, int l, int r, vector<int> &a){tr[u].l = l; tr[u].r = r;if(l == r){tr[u].sum = a[l - 1];return;}int mid = l + r >> 1;build(ls, l, mid, a);build(rs, mid + 1, r, a);pushup(u);} void pushdown(int u){if(tr[u].add){tr[ls].sum += tr[u].add * (tr[ls].r - tr[ls].l + 1);tr[rs].sum += tr[u].add * (tr[rs].r - tr[rs].l + 1);tr[ls].add += tr[u].add;tr[rs].add += tr[u].add;tr[u].add = 0;}}void modify(int u, int l, int r, int v){if(l <= tr[u].l && tr[u].r <= r){tr[u].sum += v * (tr[u].r - tr[u].l + 1);tr[u].add += v;return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(ls, l, r, v);if(r > mid) modify(rs, l, r, v);pushup(u);}int query(int u, int l, int r){if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;int ans = 0;if(l <= mid) ans += query(ls, l, r);if(r > mid) ans += query(rs, l, r);return ans;}#undef ls#undef rs
};signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<int> a(n);for(auto &i: a) cin >> i;vector<int> diff(n);diff[0] = a[0];for(int i = 1; i < n; i++) diff[i] = a[i] - a[i - 1]; segment seg(diff);for(int i = 0; i < m; i++){int op;cin >> op;if(op == 1){int l, r, k, d;cin >> l >> r >> k >> d;seg.modify(1, l, l, k);if(l + 1 <= r) seg.modify(1, l + 1, r, d);if(r < n) seg.modify(1, r + 1, r + 1, -(k + d * (r - l)));}else{int p;cin >> p;cout << seg.query(1, 1, p) << endl;}}return 0;
}