洛谷 P1438 无聊的数列

本文主要是介绍洛谷 P1438 无聊的数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给定一个序列 $A=(A_1,A_2,\cdots,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 \quad (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;
}