题意
原题链接
给定序列\(a\)，要求维护区间加，区间乘，区间查询三种操作
sol
显然线段树，事实上，这是一道板子题（luoguP3373），但由于蒟蒻实在是太蒻了，并没有打过这道题。
区间加
如果我们将区间里的每一个元素都插入线段树做一次修改操作，那么一次修改操作的时间复杂度为\(O(n \log n)\)，此时需要引入懒标记（lazytag）
当我们更新/查询到一个区间时，若这个区间的所有元素都在我们要更新/查询的区间中，即被其包含，那么我们就无需继续向下递归，而是在这个节点上记录一个lazytag。当下一次需要更新/查询其儿子时，再将lazytag向下传递
此时我们只需要处理lazytag即可
对于以下序列$$a_1, a_2, a_3, \cdots , a_n$$
此时这个序列的和为$$\sum_{i=1}^{n} a_i$$
此时，若将其中\([l, r]\)区间增加\(c\)，则序列变为
此时序列和变为$$\sum_{i=1}^{n} a_i + c(r - l + 1)$$
考虑到\(r-l+1\)可以处理出来，所以只需传递\(c\)即可
区间乘
类似于区间加，我们也可以使用lazytag进行操作
记两个lazytag，分别为\(lazymul\)和\(lazyadd\)，来处理加法和乘法的情况
若将刚才的序列中的\([l, r]\)区间乘\(v\)，则序列变为
此时序列和变为$$\sum_{1\le i \le n, i \notin [l, r]}a_i + v\cdot \sum_{l\le i \le r} a_i + v\cdot c(r - l + 1)$$
我们发现，当执行区间乘操作时，不仅\(lazymul\)需要修改，而且\(lazyadd\)也需要乘以相应的数
最终，该区间的的和即为\(tr \cdot lazymul + lazyadd\)
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100005;
LL tree[N * 4];
LL lazyadd[N * 4], lazymul[N * 4];
int a[N];
int n, m, p;
void pushup(int u){
tree[u] = tree[u << 1] + tree[u << 1 | 1];
}
void pushdown(int u, int l, int r){
if (l != r){
lazymul[u << 1] = (LL) lazymul[u << 1] * lazymul[u] % p;
lazymul[u << 1 | 1] = (LL) lazymul[u << 1 | 1] * lazymul[u] % p;
lazyadd[u << 1] = ((LL) lazyadd[u << 1] * lazymul[u] % p + lazyadd[u]) % p;
lazyadd[u << 1 | 1] = ((LL) lazyadd[u << 1 | 1] * lazymul[u] % p + lazyadd[u]) % p;
int mid = l + r >> 1;
tree[u << 1] = ((LL) tree[u << 1] * lazymul[u] % p + lazyadd[u] * (mid - l + 1)) % p;
tree[u << 1 | 1] = ((LL) tree[u << 1 | 1] * lazymul[u] % p + lazyadd[u] * (r - mid)) % p;
}
lazymul[u] = 1, lazyadd[u] = 0;
}
void build(int u, int l, int r){
lazymul[u] = 1, lazyadd[u] = 0;
if (l == r) {
tree[u] = a[l];
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void update(int u, int l, int r, int L, int R, LL val, int op){
if (L <= l && r <= R){
if (op) {
lazyadd[u] = (lazyadd[u] + val) % p;
tree[u] = (tree[u] + val * (r - l + 1)) % p;
}
else {
lazymul[u] = (LL) lazymul[u] * val % p;
lazyadd[u] = (LL) lazyadd[u] * val % p;
tree[u] = (LL) tree[u] * val % p;
}
return ;
}
pushdown(u, l, r);
int mid = l + r >> 1;
if (L <= mid) update(u << 1, l, mid, L, R, val, op);
if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val, op);
pushup(u);
}
LL query(int u, int l, int r, int L, int R){
if (L <= l && r <= R) return tree[u];
pushdown(u, l, r);
LL res = 0, mid = l + r >> 1;
if (L <= mid) res = (res + query(u << 1, l, mid, L, R)) % p;
if (R > mid) res = (res + query(u << 1 | 1, mid + 1, r, L, R)) % p;
return res;
}
int main(){
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
build(1, 1, n);
scanf("%d", &m);
while (m -- ){
int op;
int t, g, c;
scanf("%d", &op);
if (op == 1){
scanf("%d%d%d", &t, &g, &c);
update(1, 1, n, t, g, c, 0);
}
else if (op == 2){
scanf("%d%d%d", &t, &g, &c);
update(1, 1, n, t, g, c, 1);
}
else {
scanf("%d%d", &t, &g);
printf("%lld\n", query(1, 1, n, t, g));
}
}
return 0;
}
蒟蒻犯下的一些若至错误
- 建树的时候把
a[l]写成了l，结果1h没调出来 - 取模没取尽，导致最终炸int