这题能过我吃
原题链接：54995.线段树 模版二
2025-07-13 14:09:57
发布于：河北
这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃这题能过我吃
全部评论 4
#include <bits/stdc++.h>
#define MAXN 500005
#define ll long long
using 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) {
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) ChangeAdd2025-08-10 来自 广东
0#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define ll long long
int n, m, mod;
int a[MAXN];
struct Segment_Tree {
ll sum, add = 0, mul = 1;
} s[MAXN * 4];
void update(int pos) {
s[pos].sum = (s[pos << 1].sum + s[pos << 1 | 1].sum) % mod;
}
void pushdown(int pos, int l, int r, int mid) {
s[pos << 1].sum = (s[pos << 1].sum * s[pos].mul + s[pos].add * (mid - l + 1)) % mod;
s[pos << 1 | 1].sum = (s[pos << 1 | 1].sum * s[pos].mul + s[pos].add * (r - mid)) % 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;
}
void build_tree(int pos, int l, int r) {
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);
}
void ChangeMul(int pos, int l, int r, int x, int y, int k) {
if (x <= l && 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;
}
int mid = (l + r) >> 1;
pushdown(pos, l, r, mid);
if (x <= mid) ChangeMul(pos << 1, l, mid, x, y, k);
if (y > mid) ChangeMul(pos << 1 | 1, mid + 1, r, x, y, k);
update(pos);
}
void ChangeAdd(int pos, int l, int r, int x, int y, int k) {
if (x <= l && r <= y) {
s[pos].add = (s[pos].add + k) % mod;
s[pos].sum = (s[pos].sum + k * (r - l + 1)) % mod;
return;
}
int mid = (l + r) >> 1;
pushdown(pos, l, r, mid);
if (x <= mid) ChangeAdd(pos << 1, l, mid, x, y, k);
if (y > mid) ChangeAdd(pos << 1 | 1, mid + 1, r, x, y, k);
update(pos);
}
ll AskRange(int pos, int l, int r, int x, int y) {
if (x <= l && r <= y) return s[pos].sum;
int mid = (l + r) >> 1;
pushdown(pos, l, r, mid);
ll val = 0;
if (x <= mid) val = (val + AskRange(pos << 1, l, mid, x, y)) % mod;
if (y > mid) val = (val + AskRange(pos << 1 | 1, mi2025-07-30 来自 江苏
0
有帮助，赞一个