社区讨论

线段树板子全RE,不知道哪里出问题了,求调

P3372【模板】线段树 1参与者 4已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mhjau4xz
此快照首次捕获于
2025/11/03 23:32
4 个月前
此快照最后确认于
2025/11/03 23:32
4 个月前
查看原帖
幸苦大神帮忙看看哪里出了问题,全RE了
CPP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100005;
ll arr[N];
ll sum[N << 4];//累加和是数组(N << 2相当于N * 2) 
ll add[N << 4];//懒数组 

//处理懒信息 
void lazy(int i, ll v, int n) {
	sum[i] += v * n;
	add[i] += v;
}

//累加信息的汇总
void up(int i) {
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
} 

//建立线段树
void build(int l, int r, int i) {
	if (l == r) {
		sum[i] = arr[l];
	}
	else {
		int mid = l + r >> 1;
		build(l, mid, i << 1);
		build(mid + 1, r, i << 1 | 1);
		up(i);
	}
	add[i] = 0;
} 

//懒信息下发
//l ~ r i 懒
//l ~ mid  i * 2 几个数ln
//mid + 1 ~ r  i * 2 + 1 
void down(int i, int ln, int rn) {
	if (add[i] != 0) {
		lazy(i << 1, add[i], ln); 
		lazy(i << 1 | 1, add[i], rn);
		add[i] = 0;
	}
}

//范围修改,jobl ~ jobr范围上每个数字增加jobv
//这里jobl,jobr,jobv是不变的,l,r,i是不断变化的 
void addx(int jobl, int jobr, ll jobv, int l, int r, int i) {
	if (jobl <= l && r >= jobr) {
		lazy(i, jobv, r - l + 1);
	}
	else {
		int mid = l + r >> 1;
		down(i, mid - l + 1, r - mid);
		if (jobl <= mid) {
			addx(jobl, jobr, jobv, l, mid, i << 1);
		}
		if (jobr > mid) {
			addx(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);
		}
		up(i);
	} 
} 


//查询累加和 
ll query(int jobl, int jobr, int l, int r, int i) {
	if (jobl <= l && r <= jobr) return sum[i];
	int mid = l + r >> 1;
	down(i, mid - l + 1, r - mid);
	ll ans = 0;
	if (jobl <= mid) {
		ans += query(jobl, jobr, l, mid, i << 1);
	} 
	if (jobr > mid) {
		ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);
	}
	return ans;
}

int n, m;

int main() {
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	build(1, n, 1);
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int l, r, v;
			cin >> l >> r >> v;
			addx(l, r, v, 1, n, 1);
		}
		else {
			int l, r;
			cin >> l >> r;
			ll ans = query(l, r, 1, n, 1);
			cout << ans << endl;
		}
	}
	return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...