社区讨论
不明白95最后那5去哪了
P3372【模板】线段树 1参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mhjs5ls2
- 此快照首次捕获于
- 2025/11/04 07:37 4 个月前
- 此快照最后确认于
- 2025/11/04 07:37 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
struct node{
ll date = 0, lazy = 0;
};
node tree[4044444];
ll date[1011111];
int n ;
void creattree(int left, int right, int pos){
if(left == right){
tree[pos].date = date[left];
return ;
}
int mid = (left + right ) /2;
creattree(left, mid, pos*2);
creattree(mid+1, right, pos*2+1);
tree[pos].date = tree[pos*2].date + tree[pos*2+1].date;
}
void pushdown(int pos,int left, int right){
if(tree[pos].lazy != 0){
int mid = (left + right ) /2;
tree[pos*2].lazy += tree[pos].lazy;
tree[pos*2+1].lazy += tree[pos].lazy;
tree[pos*2].date += tree[pos].lazy*(mid - left + 1);
tree[pos*2+1].date += tree[pos].lazy*(right - mid);
tree[pos].lazy = 0;
}
}
ll findsum(int left, int right, int l, int r, int pos){
if(l > right || r < left){
return 0;
}
if(left >= l && right <= r){
return tree[pos].date;
}
int mid = (left + right )/2;
pushdown(pos, left , right);
ll leftmax = findsum(left, mid, l, r, pos*2);
ll rightmax = findsum(mid+1, right, l, r, pos*2+1);
return leftmax + rightmax;
}
void updaterange(int left, int right,int l, int r, int pos, int value){
if(l > right || r < left){
return ;
}
if(left >= l && right <= r){
tree[pos].lazy += value;
tree[pos].date += value * (right - left +1);
return ;
}
int mid = (left + right) /2;
pushdown(pos, left ,right);
updaterange(left, mid, l, r, pos*2, value);
updaterange(mid+1, right, l, r, pos*2+1, value);
tree[pos].date = tree[pos*2+1].date + tree[pos*2].date;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int m;
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> date[i];
creattree(1 , n , 1);
while(m--){
int a;
cin >> a;
if(a == 1){
int b,c;
ll d;
cin >> b >> c >> d;
updaterange(1, n , b, c , 1, d);
}else{
int b,c;
cin >> b >> c;
cout << findsum(1, n, b, c, 1) << "\n";
}
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...