网站主导航,网络设计方案的重要性,虚拟主机怎么用,自已能做网站建设吗【模板】线段树 2
传送门#xff1a;https://www.luogu.com.cn/problem/P3373 题单#xff1a;https://www.luogu.com.cn/training/16376#problems
题目描述
如题#xff0c;已知一个数列#xff0c;你需要进行下面三种操作#xff1a;
将某区间每一个数乘上 x x xhttps://www.luogu.com.cn/problem/P3373 题单https://www.luogu.com.cn/training/16376#problems
题目描述
如题已知一个数列你需要进行下面三种操作
将某区间每一个数乘上 x x x将某区间每一个数加上 x x x求出某区间每一个数的和。
输入格式
第一行包含三个整数 n , q , m n,q,m n,q,m分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 n n n 个用空格分隔的整数其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 q q q 行每行包含若干个整数表示一个操作具体如下
操作 1 1 1 格式1 x y k 含义将区间 [ x , y ] [x,y] [x,y] 内每个数乘上 k k k
操作 2 2 2 格式2 x y k 含义将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k
操作 3 3 3 格式3 x y 含义输出区间 [ x , y ] [x,y] [x,y] 内每个数的和对 m m m 取模所得的结果
输出格式
输出包含若干行整数即为所有操作 3 3 3 的结果。
样例 #1
样例输入 #1
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样例输出 #1
17
2提示
【数据范围】
对于 30 % 30\% 30% 的数据 n ≤ 8 n \le 8 n≤8 q ≤ 10 q \le 10 q≤10。 对于 70 % 70\% 70% 的数据$n \le 10^3 q \le 10^4$。 对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 1 ≤ q ≤ 1 0 5 1 \le q \le 10^5 1≤q≤105。
除样例外 m 571373 m 571373 m571373。
数据已经过加强 _
样例说明 故输出应为 17 17 17、 2 2 2 40 m o d 38 2 40 \bmod 38 2 40mod382。
代码
#include bits/stdc.h#define MAXN 100010
#define ll long longusing namespace std;int n, m, mod;
int a[MAXN];struct Segment_Tree {ll sum, add, mul;int l, r;
}s[MAXN * 4];void update(int pos) {s[pos].sum (s[pos 1].sum s[pos 1 | 1].sum) % mod;return;
}void pushdown(int pos) { //pushdown的维护s[pos 1].sum (s[pos 1].sum * s[pos].mul s[pos].add * (s[pos 1].r - s[pos 1].l 1)) % mod;s[pos 1 | 1].sum (s[pos 1 | 1].sum * s[pos].mul s[pos].add * (s[pos 1 | 1].r - s[pos 1 | 1].l 1)) % mod;s[pos 1].mul (s[pos 1].mul * s[pos].mul) % mod;s[pos 1 | 1].mul (s[pos 1 | 1].mul * s[pos].mul) % mod;s[pos 1].add (s[pos 1].add * s[pos].mul s[pos].add) % mod;s[pos 1 | 1].add (s[pos 1 | 1].add * s[pos].mul s[pos].add) % mod;s[pos].add 0;s[pos].mul 1;return;
}void build_tree(int pos, int l, int r) { //建树s[pos].l l;s[pos].r r;s[pos].mul 1;if (l r) {s[pos].sum a[l] % mod;return;}int mid (l r) 1;build_tree(pos 1, l, mid);build_tree(pos 1 | 1, mid 1, r);update(pos);return;
}void ChangeMul(int pos, int x, int y, int k) { //区间乘法if (x s[pos].l s[pos].r y) {s[pos].add (s[pos].add * k) % mod;s[pos].mul (s[pos].mul * k) % mod;s[pos].sum (s[pos].sum * k) % mod;return;}pushdown(pos);int mid (s[pos].l s[pos].r) 1;if (x mid) ChangeMul(pos 1, x, y, k);if (y mid) ChangeMul(pos 1 | 1, x, y, k);update(pos);return;
}void ChangeAdd(int pos, int x, int y, int k) { //区间加法if (x s[pos].l s[pos].r y) {s[pos].add (s[pos].add k) % mod;s[pos].sum (s[pos].sum k * (s[pos].r - s[pos].l 1)) % mod;return;}pushdown(pos);int mid (s[pos].l s[pos].r) 1;if (x mid) ChangeAdd(pos 1, x, y, k);if (y mid) ChangeAdd(pos 1 | 1, x, y, k);update(pos);return;
}ll AskRange(int pos, int x, int y) { //区间询问if (x s[pos].l s[pos].r y) {return s[pos].sum;}pushdown(pos);ll val 0;int mid (s[pos].l s[pos].r) 1;if (x mid) val (val AskRange(pos 1, x, y)) % mod;if (y mid) val (val AskRange(pos 1 | 1, x, y)) % mod;return val;
}int main() {scanf(%d%d%d, n, m, mod);for (int i 1; i n; i) {scanf(%d, a[i]);}build_tree(1, 1, n);for (int i 1; i m; i) {int opt, x, y;scanf(%d%d%d, opt, x, y);if (opt 1) {int k;scanf(%d, k);ChangeMul(1, x, y, k);}if (opt 2) {int k;scanf(%d, k);ChangeAdd(1, x, y, k);}if (opt 3) {printf(%lld\n, AskRange(1, x, y));}}return 0;
}
