社区讨论

感觉是spread或者modify写错了,但是具体在哪不知道

P3372【模板】线段树 1参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo32fmoj
此快照首次捕获于
2023/10/23 23:41
2 年前
此快照最后确认于
2023/10/23 23:41
2 年前
查看原帖
CPP
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 7;
int T , n , a[N] , tr[4 * N] , add[N];
void spread(int node,int start,int end)
{
	if(add[node])
	{
		int mid = start + end >> 1;
		tr[node * 2] += add[node] * (mid - start + 1);
		tr[node * 2 + 1] += add[node] * (end - mid);
		add[node * 2] += add[node];
		add[node * 2 + 1] += add[node];
		add[node] = 0;
	}
}
void modify(int node,int start,int end,int l,int r,int val)
{
	//当前节点表示区间被所求区间覆盖
	if(start >= l && end <= r)
	{
		//区间求和
		tr[node] += (end - start + 1) * val;
		//为当前节点打下懒标记、就不再下传节点了
		add[node] += val;
		return ;
	}
	spread(node , start , end);
	int mid = start + end >> 1;
	
	if(l <= mid)
	modify(node << 1 , start , mid , l , r , val);
	if(r >= mid + 1) 
	modify(node << 1 + 1, mid + 1 , end , l , r , val);
	tr[node] = tr[node * 2] + tr[node * 2 +];
}
int query(int node, int start, int end, int l,int r){
	//若目标区间与当时区间没有重叠,结束递归返回0 
	if (start > r || end < l){
		return 0;
	}
	//若目标区间包含当时区间,直接返回节点值 
	else if (l <= start && r >= end){
		return tr[node];
	}
	else {
		spread(node , start , end);
		int mid = (start + end) / 2;
		int left  = 2 * node;
		int right = 2 * node + 1;
		//计算左边区间的值 
		int sum_left = 0 , sum_right = 0;
		if(l <= mid)
		sum_left  = query(left , start, mid, l, r);
		//计算右边区间的值 
		if(r >= mid + 1)
		sum_right = query(right , mid+1, end, l, r);
		//相加即为答案 
		return sum_left + sum_right;
	} 
}
void build(int node , int start , int end)
{
	//递归边界(即遇到叶子节点)
	if(start == end){
		tr[node] = a[start];
	}
	else{
		//区间除二
		int mid = (start + end) / 2;
		//获取左右子树根节点下标
		int left = node * 2;
		int right = node * 2 + 1;
		build(left , start , mid);
		build(right , mid + 1 , end);
		tr[node] = tr[left] + tr[right];
	}
}
void solve(int c , int x)
{
	for(int i = 1 ; i <= c ; ++i) scanf("%d" , &a[i]);
	build(1 , 1 , c);
	while(x--)
	{
		int opr;
		cin>>opr;
		if(opr==1)
		{
			int r , w , q;
			cin >> r >> w >> q;
			modify(1 , 1 , c , r , w , q);
		}
		else
		{
			int r , w;
			cin >> r >> w;
			cout << query(1 , 1 , c , r , w) << endl;
		}
	}
}
int main()
{
	int c , t;
	while(cin >> c >> t)
	{
		solve(c , t);
	}
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...