Description
如题,已知一个数列,你需要进行下面三种操作:
- 将某区间每一个数乘上 xx;
- 将某区间每一个数加上 xx;
- 求出某区间每一个数的和。
Input
第一行包含三个整数 n,q,mn,q,m,分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 qq 行每行包含若干个整数,表示一个操作,具体如下:
操作 11: 格式:1 x y k
含义:将区间 [x,y][x,y] 内每个数乘上 kk
操作 22: 格式:2 x y k
含义:将区间 [x,y][x,y] 内每个数加上 kk
操作 33: 格式:3 x y
含义:输出区间 [x,y][x,y] 内每个数的和对 mm 取模所得的结果
Output
输出包含若干行整数,即为所有操作 33 的结果。
Sample 1
Inputcopy | Outputcopy |
---|---|
5 5 38 1 5 4 2 3 2 1 4 1 3 2 5 1 2 4 2 2 3 5 5 3 1 4 | 17 2 |
Hint
【数据范围】
对于 30%30% 的数据:n≤8n≤8,q≤10q≤10。
对于 70%70% 的数据:n≤103n≤103,q≤104q≤104。
对于 100%100% 的数据:1≤n≤1051≤n≤105,1≤q≤1051≤q≤105。
除样例外,m=571373m=571373。
#include <iostream>
using namespace std;
const int MAXN = 4e5 + 5; // 线段树的最大节点数,考虑n最大为10^5,4 * n即可
long long tree[MAXN]; // 存储线段树节点值
long long lazy[MAXN] = {0}; // 加法懒标记
long long lazy2[MAXN]; // 乘法懒标记
long long m; // 模数
// 下推懒标记到子节点
void push_down(int now, int l, int r) {
int mid = (l + r) >> 1; // 计算中间位置
int lroot = now << 1; // 左子节点索引
int rroot = lroot | 1; // 右子节点索引
if (lazy2[now] != 1) {
// 更新左右子节点的乘法懒标记和实际值
lazy2[lroot] = (lazy2[lroot] * lazy2[now]) % m;
lazy2[rroot] = (lazy2[rroot] * lazy2[now]) % m;
lazy[lroot] = (lazy[lroot] * lazy2[now]) % m;
lazy[rroot] = (lazy[rroot] * lazy2[now]) % m;
tree[lroot] = (tree[lroot] * lazy2[now]) % m;
tree[rroot] = (tree[rroot] * lazy2[now]) % m;
lazy2[now] = 1; // 重置当前节点的乘法懒标记
}
if (lazy[now]) {
// 更新左右子节点的加法懒标记和实际值
lazy[lroot] = (lazy[lroot] + lazy[now]) % m;
lazy[rroot] = (lazy[rroot] + lazy[now]) % m;
tree[lroot] = (tree[lroot] + lazy[now] * ((mid - l + 1)) % m) % m;
tree[rroot] = (tree[rroot] + lazy[now] * (r - mid) % m) % m;
lazy[now] = 0; // 重置当前节点的加法懒标记
}
}
// 构建线段树
void build_tree(int now, int l, int r) {
if (l == r) {
cin >> tree[now]; // 读取叶子节点的值
tree[now] %= m; // 对模数取余
} else {
int mid = (l + r) >> 1; // 计算中间位置
int lroot = now << 1; // 左子节点索引
int rroot = lroot | 1; // 右子节点索引
build_tree(lroot, l, mid); // 递归构建左子树
build_tree(rroot, mid + 1, r); // 递归构建右子树
tree[now] = (tree[lroot] + tree[rroot]) % m; // 合并左右子树的结果
}
}
// 区间乘法更新
void update_mul(int x, int y, int k, int now, int l, int r) {
if (y < l || x > r) return; // 如果在所属区间外,直接返回
if (x <= l && y >= r) { // 区间完全包含在内
lazy2[now] = (lazy2[now] * k) % m; // 更新乘法懒标记
lazy[now] = (lazy[now] * k) % m; // 更新加法懒标记
tree[now] = (tree[now] * k) % m; // 更新当前节点的值
return;
}
push_down(now, l, r); // 下推懒标记
int mid = (l + r) >> 1; // 计算中间位置
int lroot = now << 1; // 左子节点索引
int rroot = lroot | 1; // 右子节点索引
if (x <= mid) update_mul(x, y, k, lroot, l, mid); // 更新左子树
if (y > mid) update_mul(x, y, k, rroot, mid + 1, r); // 更新右子树
tree[now] = (tree[lroot] + tree[rroot]) % m; // 合并左右子树的结果
}
// 区间加法更新
void update_add(int x, int y, int k, int now, int l, int r) {
if (y < l || x > r) return; // 如果在所属区间外,直接返回
if (x <= l && y >= r) { // 区间完全包含在内
lazy[now] = (lazy[now] + k) % m; // 更新加法懒标记
tree[now] = (tree[now] + k * (r - l + 1) % m) % m; // 更新当前节点的值
return;
}
push_down(now, l, r); // 下推懒标记
int mid = (l + r) >> 1; // 计算中间位置
int lroot = now << 1; // 左子节点索引
int rroot = lroot | 1; // 右子节点索引
if (x <= mid) update_add(x, y, k, lroot, l, mid); // 更新左子树
if (y > mid) update_add(x, y, k, rroot, mid + 1, r); // 更新右子树
tree[now] = (tree[lroot] + tree[rroot]) % m; // 合并左右子树的结果
}
// 区间求和查询
long long query(int x, int y, int now, int l, int r) {
if (y < l || x > r) return 0; // 如果在所属区间外,返回0
if (x <= l && y >= r) return tree[now]; // 区间完全包含在内,返回当前节点的值
push_down(now, l, r); // 下推懒标记
int mid = (l + r) >> 1; // 计算中间位置
int lroot = now << 1; // 左子节点索引
int rroot = lroot | 1; // 右子节点索引
long long sum = 0;
if (x <= mid) sum = (sum + query(x, y, lroot, l, mid)) % m; // 查询左子树
if (y > mid) sum = (sum + query(x, y, rroot, mid + 1, r)) % m; // 查询右子树
return sum;
}
int main() {
int n, q;
cin >> n >> q >> m;
// 初始化 lazy2 数组为 1
for (int i = 0; i < 4 * n; ++i) {
lazy2[i] = 1;
}
// 初始化线段树(假设输入是1-indexed)
build_tree(1, 1, n);
for (int i = 0; i < q; ++i) {
int Q;
cin >> Q;
if (Q == 1) {
int x, y, k;
cin >> x >> y >> k;
update_mul(x, y, k, 1, 1, n); // 执行区间乘法更新
} else if (Q == 2) {
int x, y, k;
cin >> x >> y >> k;
update_add(x, y, k, 1, 1, n); // 执行区间加法更新
} else if (Q == 3) {
int x, y;
cin >> x >> y;
cout << query(x, y, 1, 1, n) << endl; // 执行区间求和查询
}
}
return 0;
}
标签:int,tree,mid,long,区间,now,p3373
From: https://blog.csdn.net/2402_86997774/article/details/145184649