You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

131 lines
3.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
/*
1.区间修改 - 乘 加
3.区间查询
存储信息:
1.区间范围l,r
2.加的懒标记add
3.乘的懒标记mul
4.区间总和sum
对于x
若对懒标记的处理是先加再乘
若此次操作为乘上一个数c
可以表示为 (n + add) * mul * c 即 (n + X) * X 的形式
若此次操作为加上一个数c
(n + add) * mul + c 不能写成 (n + X ) * X的形式
-> 无法更新新的懒标记
若对懒标记的处理是先乘再加
若此次操作是加上一个数c
可以表示为n * mul + add + c
-> 此时新的add即为add + c
若此次操作是乘上一个数c
可以表示为n * mul * c + add * c
-> 此时新的add即为add * c新的mul即为mul * c
-> 故先乘再加,以便更新懒标记
可以把乘和加的操作都看成 x * c + d
-> 若是乘法d为0
-> 若是加法c为1
若当前x的懒标记为add和mul
-> 操作可以写成(x * mul + add) * c + d
-> 即x * (mul * c) + (add * c + d)
-> 新的mul为(mul * c)新的add为(add * c + d)
注意乘的懒标记初始为1
*/
// n:N 个非负整数 p:数模 P 的值 m:操作总数
int n, p, m;
int w[N];
struct Node {
int l, r;
int sum, add, mul;
} tr[N * 4];
//子节点更新父节点统计信息
void pushup(int u) {
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p; //更新sum和信息
}
//计算函数
void eval(Node &t, int add, int mul) {
t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
t.mul = (LL)t.mul * mul % p;
t.add = ((LL)t.add * mul + add) % p;
}
void pushdown(int u) {
eval(tr[u << 1], tr[u].add, tr[u].mul); //向左儿子推送信息
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul); //向右儿子推送信息
tr[u].add = 0, tr[u].mul = 1; //清空懒标记
}
//构建
void build(int u, int l, int r) {
if (l == r) {
tr[u] = {l, r, w[r], 0, 1}; // sum=w[r],add=0,mul=1
return;
}
tr[u] = {l, r, 0, 0, 1}; // sum=0:现在无法计算出来需要等待儿孙们pushup更新 add=0,mul=1理解为默认值
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
//子节点创建完,需要更新父节点,add,mul其实不用更新是懒标记但sum是需要更新的
pushup(u);
}
//修改区间
void modify(int u, int l, int r, int add, int mul) {
if (tr[u].l >= l && tr[u].r <= r)
eval(tr[u], add, mul);
else {
pushdown(u); //向下更新一下懒标记
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, add, mul);
if (r > mid) modify(u << 1 | 1, l, r, add, mul);
//更新一下统计信息
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
return sum;
}
int main() {
cin >> n >> p;
for (int i = 1; i <= n; i++) cin >> w[i];
//构建线段树,root=1,l=1,r=n
build(1, 1, n);
cin >> m;
while (m--) {
int t, l, r, d;
cin >> t >> l >> r;
if (t == 1) { //乘
cin >> d;
modify(1, l, r, 0, d);
} else if (t == 2) { //加
cin >> d;
modify(1, l, r, d, 1);
} else //查
printf("%d\n", query(1, l, r));
}
return 0;
}