1 条题解
-
1
思路
我们可以想到用线段树,
然后维护两个懒标记 ,
表示当前子区间需要乘上 并加上 ,
注意,如果一个区间需要乘上 ,它的懒标记 也要乘上 。
下传标记需要特别注意
long long
。代码
#include <bits/stdc++.h> using namespace std; const int N = 100010; struct edge { int sum = 0; int mul = 1; int add = 0; } tr[N << 2]; int n, mod, q; int a[N]; void pushup(int u) { tr[u].sum = (1ll * tr[u << 1].sum + tr[u << 1 | 1].sum) % mod; } void addtag(int u, int l, int r, int type, int x) { if (type == 1) { tr[u].sum = (1ll * tr[u].sum * x) % mod; tr[u].add = (1ll * tr[u].add * x) % mod; tr[u].mul = (1ll * tr[u].mul * x) % mod; } else if (type == 2) { tr[u].sum = (tr[u].sum + 1ll * x * (r - l + 1)) % mod; tr[u].add = (1ll * tr[u].add + x) % mod; } } void pushdown(int u, int l, int r) { if (tr[u].mul != 1 || tr[u].add != 0) { int mid = (l + r) >> 1; tr[u << 1].add = (1ll * tr[u << 1].add * tr[u].mul) % mod; tr[u << 1 | 1].add = (1ll * tr[u << 1 | 1].add * tr[u].mul) % mod; tr[u << 1].sum = (1ll * tr[u << 1].sum * tr[u].mul) % mod; tr[u << 1 | 1].sum = (1ll * tr[u << 1 | 1].sum * tr[u].mul) % mod; tr[u << 1].mul = (1ll * tr[u << 1].mul * tr[u].mul) % mod; tr[u << 1 | 1].mul = (1ll * tr[u << 1 | 1].mul * tr[u].mul) % mod; tr[u << 1].sum = (1ll * tr[u << 1].sum + 1ll * tr[u].add * (mid - l + 1)) % mod; tr[u << 1 | 1].sum = (1ll * tr[u << 1 | 1].sum + 1ll * tr[u].add * (r - mid)) % mod; tr[u << 1].add = (1ll * tr[u << 1].add + tr[u].add) % mod; tr[u << 1 | 1].add = (1ll * tr[u << 1 | 1].add + tr[u].add) % mod; tr[u].mul = 1; tr[u].add = 0; } } void build(int u, int l, int r) { if (l == r) { tr[u].sum = a[l]; return; } int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } void modify(int u, int l, int r, int pl, int pr, int type, int x) { if (pl <= l && r <= pr) { addtag(u, l, r, type, x); return; } pushdown(u, l, r); int mid = (l + r) >> 1; if (pl <= mid) modify(u << 1, l, mid, pl, pr, type, x); if (pr > mid) modify(u << 1 | 1, mid + 1, r, pl, pr, type, x); pushup(u); } int query(int u, int l, int r, int pl, int pr) { if (pl <= l && r <= pr) return tr[u].sum; pushdown(u, l, r); int mid = (l + r) >> 1, sum = 0; if (pl <= mid) sum = (1ll * sum + query(u << 1, l, mid, pl, pr)) % mod; if (pr > mid) sum = (1ll * sum + query(u << 1 | 1, mid + 1, r, pl, pr)) % mod; return sum; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> mod; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); cin >> q; int opt, a, b, c; while (q--) { cin >> opt; if (opt == 1 || opt == 2) { cin >> a >> b >> c; modify(1, 1, n, a, b, opt, c); } else { cin >> a >> b; cout << query(1, 1, n, a, b) << '\n'; } } return 0; }
- 1
信息
- ID
- 984
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 14
- 已通过
- 4
- 上传者