题意
- 给定长度为 \(n\) 的整数序列，有以下三种操作共 \(q\) 次：
- 将区间 \([l, r]\) 每一个数乘上 \(k\)；
- 将区间 \([l, r]\) 每一个数加上 \(k\)；
- 求出区间 \([l, r]\) 的区间和对 \(m\) 取模后的结果。
- \(1 \leqslant n, q \leqslant 10^5\)。
思路
-
这个题非常明确的是要维护区间问题，我们自然而然可以想到线段树，而且维护的东西也比较明白，只用维护答案 \(ans\) 即可。
-
不过此题的难点不是线段树要维护什么，而是懒标记该怎么打？我们发现这里有加和乘两种操作，如果把两种分开的话显然会出现问题，因为乘法和加法之间是没有交换律的，那该怎么办？
-
我们发现如果完全分开是不切实际的，所以我们可以将其化为一种比较方便于更新 \(ans\) 和懒标记的形式，比如在这里懒标记就可以表示为将原本的数乘上 \(a\) 再加 \(b\)。也就是如果原本的 \(ans = x\)，那么懒标记传到此处后，\(ans = ax + b(r - l + 1)\)，因为区间内的每个元素都会乘 \(a\) 再加 \(b\)，那么它们的和肯定会先乘 \(a\) 再加 \(b \times 元素数量\)，即 \(r - l + 1\)。
-
假设原本的懒标记为 \(a,b\)，从上面传下来的为 \(a', b'\)，那么新的 \(a\) 会变为 \(a \cdot a'\)，新的 \(b\) 会变为 \(b \cdot a' + b'\)。
-
那么如果某结点懒标记向下传了，那么现在这个结点的懒标记应该是什么呢？显然现在的懒标记是要让传下去后的信息和没传一样，也就是 \(\begin{cases} a = 1 \\ b = 0 \end{cases}\) 了，这也是最开始懒标记的初始化。
时间复杂度
线段树维护区间信息，单次 \(\log n\)，共 \(q\) 次，总时间复杂度：\(O(q \log n)\)。
Code
点击查看代码
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
int ans, lazy1, lazy2;
} tr[MAXN * 4];
int n, q, m, a[MAXN];
Node Merge(Node l, Node r) {
return {(l.ans + r.ans) % m, 1, 0}; // 清空之后的懒标记
}
void update(int x, int l, int r, int a, int b) { // 更新答案及懒标记
tr[x].ans = (1ll * a * tr[x].ans + 1ll * b * (r - l + 1)) % m;
tr[x].lazy1 = 1ll * tr[x].lazy1 * a % m;
tr[x].lazy2 = (1ll * tr[x].lazy2 * a + b) % m;
}
void Pushdown(int x, int l, int r) {
int mid = (l + r) >> 1;
update(x * 2, l, mid, tr[x].lazy1, tr[x].lazy2);
update(x * 2 + 1, mid + 1, r, tr[x].lazy1, tr[x].lazy2);
tr[x] = {tr[x].ans, 1, 0};
}
void init(int i, int l, int r) {
if (l == r) {
tr[i] = {a[l], 1, 0};
return ;
}
int mid = (l + r) >> 1;
init(i * 2, l, mid), init(i * 2 + 1, mid + 1, r);
tr[i] = Merge(tr[i * 2], tr[i * 2 + 1]);
}
void modify(int i, int l, int r, int ql, int qr, int a, int b) {
if (l > qr || r < ql) {
return ;
} else if (ql <= l && r <= qr) {
update(i, l, r, a, b);
return ;
}
Pushdown(i, l, r);
int mid = (l + r) >> 1;
modify(i * 2, l, mid, ql, qr, a, b);
modify(i * 2 + 1, mid + 1, r, ql, qr, a, b);
tr[i] = Merge(tr[i * 2], tr[i * 2 + 1]);
}
Node query(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) {
return {0, 0, 0}; // 让答案不受影响
} else if (ql <= l && r <= qr) {
return tr[i];
}
Pushdown(i, l, r);
int mid = (l + r) >> 1;
return Merge(query(i * 2, l, mid, ql, qr), query(i * 2 + 1, mid + 1, r, ql, qr));
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
init(1, 1, n);
for (int t, l, r, k; q--; ) {
cin >> t >> l >> r;
if (t == 1) {
cin >> k;
modify(1, 1, n, l, r, k, 0); // 单纯的乘法是 a = k, b = 0
} else if (t == 2) {
cin >> k;
modify(1, 1, n, l, r, 1, k); // 单纯的加法是 a = 1, b = k
} else {
cout << query(1, 1, n, l, r).ans << '\n';
}
}
return 0;
}