社区讨论
感觉是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 条回复,欢迎继续交流。
正在加载回复...