社区讨论

出现了什么问题

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 条回复,欢迎继续交流。

正在加载回复...