yi105011 @ 2024-11-21 20:26:20
#include<bits/stdc++.h>
using namespace std;
long long n , m , a[100010] , op , l , r , k;
struct node {
long long l , r , num , sum;
} ans[1000010];
void build (long long l , long long r ,long long id) {
ans[id].num = ans[id].sum = 0;
ans[id].l = l; ans[id].r = r;
if (l == r) {
ans[id].num += a[l];
return;
}
long long mid = (l + r) / 2;
build (l , mid , id * 2);
build (mid + 1 , r , id * 2 + 1);
ans[id].num = ans[id * 2].num + ans[id * 2 + 1].num;
return;
}
void f1 (long long id) {
if (ans[id].r < l || r < ans[id].l) return;
if (ans[id].l == ans[id].r) {
ans[id].num += k;
return;
}
if (l <= ans[id].l && ans[id].r <= r) {
ans[id].sum = k;
ans[id].num += (ans[id].r - ans[id].l + 1) * k;
return;
}
f1 (id * 2); f1 (id * 2 + 1);
ans[id].num = ans[id * 2].num + ans[id * 2 + 1].num;
return;
}
void f2 (long long id , long long sum) {
ans[id].sum += sum;
ans[id].num += (ans[id].r - ans[id].l + 1) * sum;
if (ans[id].r < l || r < ans[id].l) return;
if (l <= ans[id].l && ans[id].r <= r) {
k += ans[id].num;
return;
}
f2 (id * 2 , ans[id].sum);
f2 (id * 2 + 1, ans[id].sum);
ans[id].sum = 0;
return;
}
int main() {
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
build (1 , n , 1);
while (m --) {
cin >> op >> l >> r;
if (op == 1) {
cin >> k;
f1 ( 1 );
}
else {
k = 0;
f2 (1 , 0);
/*for (int i = 1;i <= 9;i ++) {
cout << ans[i].l << " ~ " << ans[i].r << " = " << ans[i].num << '\n';
}*/
cout << k << '\n';
}
}
return 0;
};提交记录
by chenxi2009 @ 2024-11-21 20:38:40
@yi105011 你的标记下传操作呢？
by chenxi2009 @ 2024-11-21 20:40:26
@yi105011 另：在非建树操作中，判断当前区间长度是否为 1 是没有意义的，这种情况被判断当前结点区间是询问区间的子区间这种情况覆盖。
by chenxi2009 @ 2024-11-21 20:41:24
my article with code
by yi105011 @ 2024-11-21 20:41:33
@chenxi2009 f2函数中的sum就是下传操作啊
by chenxi2009 @ 2024-11-21 20:43:09
@yi105011 f1 中缺失标记下传。每当你需要访问子结点的时候，都要确保它的值是正确的（获得了正确下传的标记）。
by chenxi2009 @ 2024-11-21 20:48:17
@yi105011 因为在任何修改和询问操作中，我们都需要用到标记下传，所以建议为它专门写一个函数 void pushdown(int id) 表示 id 结点把标记传给儿子。
可以参考我的专栏。
by yi105011 @ 2024-11-21 20:48:46
@chenxi2009 我f1函数中
f1 (id * 2);
f1 (id * 2 + 1);就是下传标记啊
by chenxi2009 @ 2024-11-21 20:51:46
@yi105011 也许我们对下传的理解不同？下传是要你通过当前结点的 sum(标记)，更新儿子结点的 sum 和 num，并且清空当前已经下传的标记。
by chenxi2009 @ 2024-11-21 20:55:59
@yi105011 用你的代码修改了 f1 和 f2，AC 了。
#include<bits/stdc++.h>
using namespace std;
long long n , m , a[100010] , op , l , r , k;
struct node {
long long l , r , num , sum;
} ans[1000010];
void build (long long l , long long r ,long long id) {
ans[id].num = ans[id].sum = 0;
ans[id].l = l; ans[id].r = r;
if (l == r) {
ans[id].num += a[l];
return;
}
long long mid = (l + r) / 2;
build (l , mid , id * 2);
build (mid + 1 , r , id * 2 + 1);
ans[id].num = ans[id * 2].num + ans[id * 2 + 1].num;
return;
}
void f1 (long long id) {
if (ans[id].r < l || r < ans[id].l) return;
if (l <= ans[id].l && ans[id].r <= r) {
ans[id].sum += k;
ans[id].num += (ans[id].r - ans[id].l + 1) * k;
return;
}
if(ans[id].sum){
ans[id << 1].num += ans[id].sum * (ans[id << 1].r - ans[id << 1].l + 1);
ans[id << 1 | 1].num += ans[id].sum * (ans[id << 1 | 1].r - ans[id << 1 | 1].l + 1);
ans[id << 1].sum += ans[id].sum;
ans[id << 1 | 1].sum += ans[id].sum;
ans[id].sum = 0;
}
f1 (id * 2); f1 (id * 2 + 1);
ans[id].num = ans[id * 2].num + ans[id * 2 + 1].num;
return;
}
void f2 (long long id) {
if (ans[id].r < l || r < ans[id].l) return;
if (l <= ans[id].l && ans[id].r <= r) {
k += ans[id].num;
return;
}
if(ans[id].sum){
ans[id << 1].num += ans[id].sum * (ans[id << 1].r - ans[id << 1].l + 1);
ans[id << 1 | 1].num += ans[id].sum * (ans[id << 1 | 1].r - ans[id << 1 | 1].l + 1);
ans[id << 1].sum += ans[id].sum;
ans[id << 1 | 1].sum += ans[id].sum;
ans[id].sum = 0;
}
f2 (id * 2);
f2 (id * 2 + 1);
return;
}
int main() {
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
build (1 , n , 1);
while (m --) {
cin >> op >> l >> r;
if (op == 1) {
cin >> k;
f1 ( 1 );
}
else {
k = 0;
f2 (1);
/*for (int i = 1;i <= 9;i ++) {
cout << ans[i].l << " ~ " << ans[i].r << " = " << ans[i].num << '\n';
}*/
cout << k << '\n';
}
}
return 0;
};by chenxi2009 @ 2024-11-21 20:57:05
只是加了这个下传：
if(ans[id].sum){
ans[id << 1].num += ans[id].sum * (ans[id << 1].r - ans[id << 1].l + 1);
ans[id << 1 | 1].num += ans[id].sum * (ans[id << 1 | 1].r - ans[id << 1 | 1].l + 1);
ans[id << 1].sum += ans[id].sum;
ans[id << 1 | 1].sum += ans[id].sum;
ans[id].sum = 0;
}