传送门

描述

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

输入

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b” means querying the sum of Aa, Aa+1, … , Ab.

输出

You need to answer all Q commands in order. One answer in a line.

样例

Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Output
4
55
9
15

思路

题意：给1到n个数，输入Q，则询问[x,y]区间和；输入C，则在区间[x,y]加上z；

线段树，区间修改区间查询

Code

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

#include
         
           #include
          
            #define LL long long #define INIT(a,b) memset(a,b,sizeof(a)) struct Tree{
         	LL num,k,l,r; }tree[400007]; void build(LL l,LL r,LL d){   //建树 	tree[d]=(Tree){
        0,0,l,r}; 	if(l==r){
        		scanf("%lld",&tree[d].num ); 		return ; 	} 	LL mid=(l+r)/2; 	build(l,mid,d<<1); 	build(mid+1,r,d<<1|1); 	tree[d].num=tree[d<<1].num+tree[d<<1|1].num; } void down(LL d){              //标记下传并更新子节点的值 	tree[d<<1].k+=tree[d].k; 	tree[d<<1|1].k+=tree[d].k; 	tree[d<<1].num+=tree[d].k*(tree[d<<1].r-tree[d<<1].l+1); 	tree[d<<1|1].num+=tree[d].k*(tree[d<<1|1].r-tree[d<<1|1].l+1); 	tree[d].k=0; } void add(LL l,LL r,LL a,LL d){  //区间更新 	if(tree[d].l==l&&tree[d].r==r){
        		tree[d].num+=a*(tree[d].r-tree[d].l+1); 		tree[d].k+=a; 		return; 	} 	if(tree[d].k)down(d); 	LL mid=(tree[d].l+tree[d].r)/2; 	if(mid>=r) add(l,r,a,d<<1); 	else if(mid
           
            =r) return find(l,r,d<<1); 	else if(mid

转载地址：https://blog.csdn.net/cpongo3/article/details/89334368 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

传送门

描述

输入

输出

样例

思路

Code

发表评论

最新留言

关于作者

推荐文章