社区讨论

不明白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 条回复,欢迎继续交流。

正在加载回复...