这道题十分简单
2023-11-02 17:44:43
发布于:浙江
28阅读
1回复
2点赞
考虑到精度不够我们可以使用线段树将其转换为区间求和问题
以下是代码:
#include <bits/stdc++.h>
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
using namespace std;
struct SegmentTree {
int l, r; //区间左右端点
long long sum, add; //sum 区间和 add 延迟标记
} tree[400010];
int a[100010], n = 1, m = 2;
void build (int p, int l, int r) {
l(p) = l, r(p) = r;
if(l == r) {sum(p) = a[l]; return;}
int mid = l + r >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
void spread(int p) {
if(add(p)) { //节点p有标记
sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1); //更新左子节点信息
sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1); //更新右子节点
add(p * 2) += add(p); //给左子节点打延迟标记
add(p * 2 + 1) += add(p); //给右子节点打延迟标记
add(p) = 0; //清除p的标记
}
}
void change(int p, int l, int r, int d) {
if(l <= l(p) && r >= r(p)) { //完全覆盖
sum(p) += (long long) d * (r(p) - l(p) + 1); //更新节点信息
add(p) += d; //给节点打延迟标记
return;
}
spread(p); //下传延迟标记
int mid = l(p) + r(p) >> 1;
if(l <= mid) change(p * 2, l, r, d);
if(r > mid) change(p * 2 + 1, l, r, d);
sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
long long ask(int p, int l, int r) {
if(l <= l(p) && r >= r(p)) return sum(p);
spread(p);
int mid = l(p) + r(p) >> 1;
long long val = 0;
if(l <= mid) val += ask(p * 2, l, r);
if(r > mid) val += ask(p * 2 + 1, l, r);
return val;
}
int main() {
a[1] = 0;
build(1, 1, n);
while(m--) {
int d = 0;
scanf("%d", &d);
change(1, 1, 1, d);
}
printf("%lld\n", ask(1, 1, 1));
return 0;
}
全部评论 1
对了,不要直接复制,自己打一遍,不会的查一查你就可以做 普及+/提高 的题了
2023-11-02 来自 浙江
0
有帮助,赞一个