题目链接：?problem=1164
World is getting more evil and it’s getting tougher to get into the Evil League of Evil. Since the legendary Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a PhD in horribleness (but not in Computer Science). You are given an array ofnelements,which are initially all0. After that you will be givenqcommands. They are –
1.0 x y v- you have to addvto all numbers in the range ofxtoy(inclusive), wherexandyare two indexes of the array.
2.1 x y- output a line containing a single integer which is the sum of all the array elements betweenxandy(inclusive).
The array is indexed from0ton – 1.
Input
Input starts with an integerT (≤ 5), denoting the number of test cases.
Each case contains two integersn (1 ≤ n ≤ 105)andq (1 ≤ q ≤ 50000). Each of the nextqlines contains a task in one of the following form:
0 x y v (0 ≤ x ≤ y < n, 1 ≤ v ≤ 1000)
1 x y (0 ≤ x ≤ y < n)
Output
For each case, print the case number first. Then for each query’1 x y’, print the sum of all the array elements betweenxandy.
Sample InputOutput for Sample Input
2
10 5
0 0 9 10
1 1 6
0 3 7 2
0 4 5 1
1 5 5
20 3
0 10 12 1
1 11 12
1 19 19
Case 1:
60
13
Case 2:
2
0
代码如下：
#include <cstdio>#include <algorithm>using namespace std;#define lson l , mid , rt << 1#define rson mid + 1 , r , rt << 1 | 1#define LL __int64const LL maxn = 111111;LL add[maxn<<2];LL sum[maxn<<2];//求和void PushUp(LL rt){sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void PushDown(LL rt,LL len){if (add[rt]){add[rt<<1] += add[rt];add[rt<<1|1] += add[rt];sum[rt<<1] += add[rt] * (len – (len >> 1));sum[rt<<1|1] += add[rt] * (len >> 1);//更新右儿子的和add[rt] = 0;}}void build(LL l,LL r,LL rt){add[rt] = 0;//初始化为所有结点未被标记if (l == r){//scanf("%lld",&sum[rt]);sum[rt] = 0;return ;}LL mid = (l + r) >> 1;build(lson);build(rson);PushUp(rt);}void update(LL L,LL R,LL c,LL l,LL r,LL rt){if (L <= l && r <= R){add[rt] += c;sum[rt] += (LL)c * (r – l + 1);//更新代表某个区间的节点和，，该节点不一定是叶子节点return ;}PushDown(rt , r – l + 1);LL mid = (l + r) >> 1;if (L <= mid)update(L , R , c , lson);//更新左儿子if (mid < R)update(L , R , c , rson);//更新右儿子PushUp(rt);}LL query(LL L,LL R,LL l,LL r,LL rt){if (L <= l && r <= R){return sum[rt];}PushDown(rt , r – l + 1);LL mid = (l + r) >> 1;LL ret = 0;if (L <= mid)ret += query(L , R , lson);if (mid < R)ret += query(L , R , rson);return ret;}int main(){LL N , Q;LL t;LL cas = 0;scanf("%lld",&t);while(t–){scanf("%lld%lld",&N,&Q);//N为节点数build(1 , N , 1); //建树printf("Case %d:\n",++cas);while (Q–)//Q为询问次数{//char op[2];LL op;LL a , b , c;scanf("%lld",&op);if(op == 1){scanf("%lld%lld",&a,&b);printf("%lld\n",query(a+1 , b+1 , 1 , N , 1));}else if(op == 0){scanf("%lld%lld%lld",&a,&b,&c);//c为区间a到b增加的值update(a+1 , b+1 , c , 1 , N , 1);}}}return 0;}/*210 50 0 9 101 0 60 3 7 20 4 5 11 5 520 30 10 12 11 11 121 19 19*/
失败是成功之母
