听灌多,求调P3372代码
  • 板块灌水区
  • 楼主M_Jun
  • 当前回复21
  • 已保存回复22
  • 发布时间2024/12/7 16:08
  • 上次更新2024/12/7 18:36:50
查看原帖
听灌多,求调P3372代码
1098953
M_Jun楼主2024/12/7 16:08

rt,P3372【模板】线段树 1 求助

代码如下,因 RE 而爆零,
报错显示 Segmentation fault with invalid memory reference内存引用无效的分段错误

求调

#include <iostream>
#include <cmath>

#define int long long

using namespace std ;

const int N = 1e7 ;

int n, m ;
int num[N] ;

int way, l, r, x ;

struct Node_tree {
	int l, r ;
	int maxn, sum ;
	int lazy ;
} tree[4 * N + 5] ;

//建线段树
void build(int id, int l, int r) {
	tree[id].l = l ; tree[id].r = r ;
	if(l == id && r == id) { // 对叶子结点的特判 
		tree[id].sum = num[id] ;
	} else {
		register int mid = (l + r) >> 1 ;
		build(id * 2, l, mid) ; //建造左子树 
		build(id * 2 + 1, mid + 1, r) ; //建造右子树
	}
}

//数据上传 
void push_up(int id) {
	tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum ;
	tree[id].maxn = max(tree[id * 2].maxn, tree[id * 2 + 1].maxn) ;
}

//数据下传
void push_down(int id, int l, int r) {
	if(tree[id].lazy >= 0) { //若 lazy标记存在 
		register int mid = (l + r) >> 1 ;
		tree[id * 2].lazy += tree[id].lazy ; //更新左子树 lazy值
		tree[id * 2 + 1].lazy += tree[id].lazy ; //更新右子树 lazy值
		tree[id * 2].sum += tree[id].lazy * (mid - l + 1) ; // 更新左子树 sum值 
		tree[id * 2 + 1].sum += tree[id].lazy * (r - mid) ; // 更新右子树 sum值
		tree[id * 2].maxn += tree[id].lazy * (mid - l + 1) ; // 更新左子树 max值 
		tree[id * 2 + 1].maxn += tree[id].lazy * (r - mid) ; // 更新右子树 max值  
	}
}

//区间修改 
void change(int id, int l, int r, int x) {
	//当前到了编号为 id 的节点,要把 [l..r] 区间中的所有元素的值 +x
	if(l <= tree[id].l && r >= tree[id].r) {
		//如果当前节点的区间被完全包含于要更新的区间内
		tree[id].sum += (tree[id].r - tree[id].l + 1) * x ; //更新该区间的 sum
		tree[id].lazy += x ; // lazy标记叠加
		return ; 
	}
	push_down(id, tree[id].l, tree[id].r) ;
	register int mid = (tree[id].l + tree[id].r) >> 1 ;
	if(l <= mid) change(id * 2, l, r, x) ; //如果左子树与需要更新的区间有交集
	if(r >  mid) change(id * 2 + 1, l, r, x) ;//如果右子树与需要更新的区间有交集
	push_up(id) ; //更新父节点
}

//区间查询 
int query(int id, int l, int r) {
	//当前到了编号为 id 的节点,查询 [l..r] 的和
	if(l <= tree[id].l && r > tree[id].r) return tree[id].sum ; //如果当前区间完全包含于查询区间,那么直接返回
	push_down(id, l, r) ; // 每次访问都去检查lazy标记
	register int res = 0 ;
	register int mid = (l + r) >> 1 ;
	if(l <= mid) res += query(id * 2, l, r) ; //如果左子区间与查询区间有交集
	if(r <= mid) res += query(id * 2 + 1, l, r) ; //如果右子区间与查询区间有交集
	return res ;
}

signed main ( ) {
	
	cin >> n >> m ;
	for(register int i = 1 ; i <= n ; i ++) 
		cin >> num[i] ;
	
	build(1, 1, n) ;
	
	for(register int i = 1 ; i <= m ; i ++) {
		cin >> way >> l >> r ;
		if(way == 1) {
			cin >> x ;
			change(1, l, r, x) ;
		} else if(way == 2) 
			cout << query(1, l, r) << '\n' ;
	}
	
	return 0 ;
}
2024/12/7 16:08
加载中...