社区讨论
线段树板子全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 条回复,欢迎继续交流。
正在加载回复...