LightOJ - 1164 - Horrible Queries

1. #include <bits/stdc++.h>
2. #define C 100003
3. using namespace std;
4.  
5. struct data{
6.     long long sum, prop;
7. }Tree[C*3];
8.  
9. void Update(int B, int E, int Node, int x, int y, int v){
10.     if(B >= x && E <= y){
11.         Tree[Node].sum += (long long)((E-B+1)*v);
12.         Tree[Node].prop += (long long)v;
13.         return;
14.     }
15.     if(B > E || B > y || E < x)return;
16.     int Mid = (B+E) >> 1, Left = Node << 1, Right = Left+1;
17.     Update(B, Mid, Left, x, y, v);
18.     Update(Mid+1, E, Right, x, y, v);
19.     Tree[Node].sum = Tree[Left].sum + Tree[Right].sum + (long long)(E-B+1)*Tree[Node].prop;
20. }
21.  
22. long long Query(int B, int E, int Node, int x, int y, long long Carry = 0LL){
23.     if(B >= x && E <= y)return Tree[Node].sum + (long long)(E-B+1)*Carry;
24.     if(B > E || B > y || E < x)return 0LL;
25.     int Mid = (B+E)>>1, Left = Node<<1, Right = Left+1;
26.     long long p = Query(B, Mid, Left, x, y, Carry+Tree[Node].prop);
27.     long long q = Query(Mid+1, E, Right, x, y, Carry+Tree[Node].prop);
28.     return p+q;
29. }
30.  
31. int main(){
32.     int T, N, Q, F, X, Y, V, CS = 0;
33.     scanf("%d", &T);
34.     while(T--){
35.         scanf("%d %d", &N, &Q);
36.         memset(Tree, 0, sizeof(Tree));
37.         printf("Case %d:\n", ++CS);
38.         for(int i = 1; i <= Q; i++){
39.             scanf("%d", &F);
40.             if(F == 0){
41.                 scanf("%d %d %d", &X, &Y, &V);
42.                 Update(0, N-1, 1, X, Y, V);
43.             }
44.             else{
45.                 scanf("%d %d", &X, &Y);
46.                 printf("%lld\n", Query(0, N-1, 1, X, Y));
47.             }
48.         }
49.     }
50.     return 0;
51. }