Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


[codevs]1082线段树3

线段树区间修改求和模板

题目链接

题目描述

给你N个数,有两种操作:
1:给区间[a,b]的所有数增加X
2:询问区间[a,b]的数的和。

输入描述

第一行一个正整数n,接下来n行n个整数,
再接下来一个正整数Q,每行表示操作的个数,
如果第一个数是1,后接3个正整数,
表示在区间[a,b]内每个数增加X,如果是2,
表示操作2询问区间[a,b]的和是多少。

输出描述

对于每个询问,每行输出一个答案

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<iomanip>
#define LL long long
using namespace std;
const int maxn=100000+10;
LL change[maxn<<2],sum[maxn<<2];

void pushup(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}

void pushdown(int rt,int l,int r){
if(change[rt]){
int mid = (l+r)>>1;
change[rt<<1] += change[rt];
change[rt<<1|1] += change[rt];
sum[rt<<1] += change[rt]*(mid-l+1);
sum[rt<<1|1] += change[rt]*(r-mid);
change[rt] = 0;
}
}

void update(int L,int R,int c,int l,int r,int rt){
if(L<=l && r<=R){
change[rt] += c;
sum[rt] += (LL)c*(r-l+1);
return ;
}
pushdown(rt,l,r);
int mid = (l+r)>>1;
if(L <= mid) update(L,R,c,l,mid,rt<<1);
if(mid < R) update(L,R,c,mid+1,r,rt<<1|1);
pushup(rt);
}

LL query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R)
return sum[rt];
pushdown(rt,l,r);
LL ans = 0;
int mid = (l+r)>>1;
if(L <= mid) ans += query(L,R,l,mid,rt<<1);
if(mid < R) ans += query(L,R,mid+1,r,rt<<1|1);
return ans;
}

void build(int l,int r,int rt){
change[rt] = 0;
if(l == r){
scanf("%lld",&sum[rt]);
return ;
}
int mid = (l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}

int main(){
int n,m,p,x,y,z;
scanf("%d%d",&n,&m);
build(1,n,1);
while(m--){
scanf("%d",&p);
if(p == 2){
scanf("%d%d",&x,&y);
printf("%lld\n",query(x,y,1,n,1));
}
else {
scanf("%d%d%d",&x,&y,&z);
update(x,y,z,1,n,1);
}
}
return 0;
}

Markdown

最近的文章

洛谷P1083借教室

题目链接题目描述 在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。 面对海量租借教室的信息,我们自然希望编程解决这个问题。 我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租 …

于  线段树 继续阅读
更早的文章

codevs伊吹萃香

题目链接题目描述 在幻想乡,伊吹萃香是能够控制物体密度的鬼王。因为能够控制密度,所以萃香能够制造白洞和黑洞,并可以随时改变它们。某一天萃香闲着无聊,在妖怪之山上设置了一些白洞或黑洞,由于引力的影响,给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路,来方便进出。已知妖怪之山上有N个路口( …

于  最短路 继续阅读