题目描述
如题，已知一个数列，你需要进行下面三种操作：
将某区间每一个数乘上 x
将某区间每一个数加上 x
求出某区间每一个数的和
输入格式
第一行包含三个整数 n , m , p 分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i项的初始值。
接下来 m 行每行包含若干个整数，表示一个操作，具体如下：
操作 1： 格式：1 x y k含义：将区间 [ x , y] 内每个数乘上 k
操作 2 ： 格式：2 x y k含义：将区间 [ x , y ]内每个数加上 k
操作 3 ： 格式：3 x y含义：输出区间 [ x , y ]内每个数的和对 p 取模所得的结果
输出格式
输出包含若干行整数，即为所有操作 3 的结果。
输入输出样例
输入 #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
代码
结构体
#include <bits/stdc++.h> using namespace std; const int N = 100010; typedef long long LL; #define ls u<<1 #define rs u<<1|1 struct node { int l, r; int add, mul, sum; } tr[N << 2]; int n, m, mod; int a[N]; // *x +y int calc(int u, int x, int y) { tr[u].sum = ((LL)tr[u].sum * x + (LL)(tr[u].r - tr[u].l + 1) * y) % mod; tr[u].add = ((LL)tr[u].add * x + y) % mod; tr[u].mul = ((LL)tr[u].mul * x) % mod; } void pushup(int u) { tr[u].sum = ((LL)tr[ls].sum + tr[rs].sum) % mod; } void pushdown(int u) { int x = tr[u].mul, y = tr[u].add; calc(ls, x, y), calc(rs, x, y); tr[u].add = 0, tr[u].mul = 1; } void build(int u, int l, int r) { tr[u] = {l, r, 0, 1}; if(l == r) { tr[u].sum = a[l]; return ;} int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } void modify(int u, int l, int r, int x, int y) { if(tr[u].l >= l && tr[u].r <= r) { calc(u, x, y); return ; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(ls, l, r, x, y); if(r > mid) modify(rs, l, r, x, y); 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 v = 0; if(l <= mid) v = query(ls, l, r); if(r > mid) v = ((LL)v + query(rs, l, r)) % mod; return v % mod; } int main() { cin >> n >> m >> mod; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); // cin >> m; int op, x, y, k; while(m--) { cin >> op >> x >> y; if(op == 1) { cin >> k; modify(1, x, y, k, 0); } else if(op == 2) { cin >> k; modify(1, x, y, 1, k); } else if(op == 3) { cout << query(1, x, y) << endl; } } return 0; }
- 数组
#include<bits/stdc++.h> using namespace std; #define ls u<<1 #define rs u<<1|1 #define LL long long const int N = 1000010; int n, m, Mod, a[N], L[N << 2], R[N << 2], tr[N << 2], add[N << 2], mul[N << 2]; void pushup(int u) { tr[u] = (tr[ls] + tr[rs]) % Mod; } // +p *q void calc(int u, int p, int q) { tr[u] = ((LL)tr[u] * q + (LL)(R[u] - L[u] + 1) * p) % Mod; add[u] = ((LL)add[u] * q + p) % Mod; mul[u] = (LL)mul[u] * q % Mod; } void pushdown(int u) { int p = add[u], q = mul[u]; calc(ls, p, q), calc(rs, p, q); add[u] = 0, mul[u] = 1; } void build(int u, int l, int r) { L[u] = l, R[u] = r; if(l == r) { tr[u] = a[l]; add[u] = 0, mul[u] = 1; return ; } int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); add[u] = 0, mul[u] = 1; pushup(u); } // +p *q void modify(int u, int l, int r, int p, int q) { int ll = L[u], rr = R[u]; if(ll >= l && rr <= r) { calc(u, p, q); return ; } pushdown(u); int mid = ll + rr >> 1; if(l <= mid) modify(ls, l, r, p, q); if(r > mid) modify(rs, l, r, p, q); pushup(u); } int query(int u, int l, int r) { int ll = L[u], rr = R[u]; if(ll >= l && rr <= r) { return tr[u]; } pushdown(u); int mid = ll + rr >> 1; int ans = 0; if(l <= mid) ans = query(ls, l, r); if(r > mid) ans = ((LL)ans + query(rs, l, r)) % Mod; return ans; } int main() { scanf("%d%d%d", &n, &m, &Mod); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); int op, x, y, k; while(m--) { scanf("%d%d%d", &op, &x, &y); if(op == 1) { scanf("%d", &k); modify(1, x, y, 0, k); } else if(op == 2) { scanf("%d", &k); modify(1, x, y, k, 1); } else { printf("%d\n", query(1, x, y)); } } return 0; }
