社区讨论
出现了什么问题
P3373【模板】线段树 2参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhjtftph
- 此快照首次捕获于
- 2025/11/04 08:13 4 个月前
- 此快照最后确认于
- 2025/11/04 08:13 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 100010;
int n, m, a[maxn];
struct node { //一个线段树节点
//第一个要修改的地方:标记的定义
int sum;//代表区间和
int size;//代表区间长度
int mul;//这段区间被整体乘了多少
int add;
node() {
//第二个要修改的地方:标记的初始化
sum = size = add = 0;
mul = 1;
}
void init(long long v) { //用一个数初始化
sum = v;
size = 1;
}
} z[maxn << 2]; //z[i]就代表线段树的第i个节点
node operator+(const node &l, const node &r) {
node res;
res.sum = l.sum + r.sum;
res.size = l.size + r.size;
return res;
}
void colormul(int l, int r, int rt, int v) {
//第三个要修改的地方:打标记
z[rt].mul *= v;
z[rt].sum *= v;
}
void coloradd(int l, int r, int rt, int v) {
z[rt].add += v;
z[rt].sum += z[rt].size * v;
}
void push_col(int l, int r, int rt) { //标记下放 把标记告诉儿子
//第四个要修改的地方:下放标记
int m = (l + r) >> 1;
if (z[rt].mul != 1){
colormul(lson, z[rt].mul);
colormul(rson, z[rt].mul);
z[rt].mul = 1;
}
else if(z[rt].add != 0){
coloradd(lson, z[rt].add);
coloradd(rson, z[rt].add);
z[rt].add = 0;
}
}
void build(int l, int r, int rt) //建树 初始化l,r,rt这个节点
//编号为rt的线段树节点 所对应的区间是l~r
{
if (l == r) {
z[rt].init(a[l]);
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
node query(int l, int r, int rt, int nowl, int nowr)
//l,r,rt描述了一个线段树节点
//nowl nowr代表了询问的区间的左端点和右端点
{
if (nowl <= l && r <= nowr) return z[rt];
push_col(l, r, rt);
int m = (l + r) >> 1;
if (nowl <= m) {
if (m < nowr) return query(lson, nowl, nowr) + query(rson, nowl, nowr);
else return query(lson, nowl, nowr);
} else return query(rson, nowl, nowr);
}
void modify(int l, int r, int rt, int nowl, int nowr, int addv, int mulv)
//把nowl~nowr这段区间全部整体+v
{
if (nowl <= l && r <= nowr) { //当前线段树节点被修改区间整体包含
coloradd(l, r, rt, addv);//给l,r,rt这个节点打一个+v的懒标记
colormul(l, r, rt, mulv);
return;
}
push_col(l, r, rt);
int m = (l + r) >> 1;
if (nowl <= m) {
modify(lson, nowl, nowr, addv, 1);
modify(lson, nowl, nowr, 0, mulv);
}
if (m < nowr){
modify(rson, nowl, nowr, addv, 1);
modify(rson, nowl, nowr, 0, mulv);
}
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
int opt;
cin >> opt;
if (opt == 1) {
long long l, r, k;
cin >> l >> r >> k;
modify(1, n, 1, l, r, 0, k);
} else if (opt == 2) {
long long l, r, k;
cin >> l >> r >> k;
modify(1, n, 1, l, r, k, 1);
} else if (opt == 3) {
long long l, r;
cin >> l >> r;
cout << query(1, n, 1, l, r).sum << '\n';
}
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...