社区讨论
为什么全部WA了啊
P3372【模板】线段树 1参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lod9xw4h
- 此快照首次捕获于
- 2023/10/31 03:09 2 年前
- 此快照最后确认于
- 2023/11/05 13:35 2 年前
代码如下,样例的第三个回答错了
CPP#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll n, m, a[N], add[4 * N], sum[4 * N];
inline ll read() {
ll n = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if(c == '-') f = (~ f + 1);
c = getchar();
}
while (c >= '0' && c <= '9') {
n = (n << 3) + (n << 1) + (c ^ 48);
c = getchar();
}
return n * f;
}
inline void build(ll k, ll l, ll r) { // 建树
if(l == r) {
sum[k] = a[l];
return;
}
ll mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
sum[k] = sum[k << 1] + sum[k << 1 | 1];
return;
}
inline void Add(ll k, ll l, ll r, ll val) {
add[k] += val;
sum[k] += val * (r - l + 1);
}
inline void push_down(ll k, ll l, ll r, ll mid) { // 懒标记
if(!add[k]) return ;
Add(k << 1, l, mid, add[k]);
Add(k << 1 | 1, mid + 1, r, add[k]);
add[k] = 0;
}
inline ll query(ll k, ll l, ll r, ll x, ll y) { // 区间查询
if(x <= l && r <= y)
return sum[k];
ll res = 0;
ll mid = (l + r) >> 1;
push_down(k, l, r, sum[k]);
if(x <= mid) res += query(k << 1, l, mid, x, y);
if(y > mid) res += query(k << 1 | 1, mid + 1, r, x, y);
return res;
}
inline void modify(ll k, ll l, ll r, ll x, ll y, ll val) { // 区间修改
if(x <= l && r <= y) {
Add(k, l, r, val);
return ;
}
ll mid = (l + r) >> 1;
push_down(k, l, r, mid);
if(x <= mid) modify(k << 1, l, mid, x, y, val);
if(y > mid) modify(k << 1 | 1, mid + 1, r, x, y, val);
sum[k] = sum[k << 1] + sum[k << 1 | 1];
return ;
}
int main() {
n = read();
m = read();
for (ll i = 1; i <= n; ++ i)
a[i] = read();
build(1, 1, n);
ll opt, x, y, k;
for (ll i = 1; i <= m; ++ i) {
opt = read();
if(opt == 1) {
x = read(); y = read(); k = read();
modify(1, 1, n, x, y, k);
}
else { // opt == 2
x = read(); y = read();
printf("%d\n", query(1, 1, n, x, y));
}
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...