fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. #define LL long long
  7. #define LIMIT 263000
  8.  
  9. LL segment_tree[LIMIT];
  10.  
  11. LL lazy[LIMIT];
  12.  
  13. void build(int t,int i,int j)
  14. {
  15. 	if(i==j)
  16. 	{
  17. 		segment_tree[t]= 0;
  18. 		lazy[t] = segment_tree[t];
  19. 		return;
  20. 	}
  21. 	int left = t<<1;
  22. 	int right = left|1;
  23. 	int mid = (i+j)>>1;	
  24. 	build(left, i, mid);
  25. 	build(right, mid+1, j);
  26. 	segment_tree[t]= segment_tree[left] + segment_tree[right];
  27. 	lazy[t] = segment_tree[t];
  28. }
  29.  
  30. void lazy_propagate(int t, int i, int j)
  31. {
  32.     if(lazy[t]!=0)
  33.     {
  34.         segment_tree[t] += (j-i+1)*lazy[t];
  35.         if(i!=j)
  36.         {
  37.             int left = t<<1;
  38.             int right = left|1;
  39.             lazy[left] += lazy[t];
  40.             lazy[right] += lazy[t];
  41.         }
  42.         lazy[t]=0;
  43.     }
  44. }
  45.  
  46. void update(int t, int i, int j, int a, int b, LL v)
  47. {
  48.     lazy_propagate(t, i, j);
  49.     if(i>j || i>b || j<a)
  50.         return ;
  51.     if(i>=a && j<=b)
  52.     {
  53.         lazy[t] = v;
  54.         lazy_propagate(t, i, j);
  55.         return ;
  56.     }
  57. 	int left = t<<1;
  58. 	int right = left|1;
  59. 	int mid = (i+j)>>1;	
  60.     update(left, i, mid, a, b, v);
  61.     update(right, mid+1, j, a, b, v);
  62.     segment_tree[t] = segment_tree[left] + segment_tree[right];
  63. }
  64.  
  65. LL query(int t, int i, int j, int a, int b)
  66. {
  67.     lazy_propagate(t, i, j);
  68.     if(i>j || i>b || j<a)
  69.         return 0;
  70.     if(i>=a && j<=b)
  71.         return segment_tree[t];
  72. 	int left = t<<1;
  73. 	int right = left|1;
  74. 	int mid = (i+j)>>1;	
  75.     return query(left, i, mid, a, b) + query(right, mid+1, j, a, b);
  76. }
  77.  
  78. int main()
  79. {
  80.     int t;
  81.     scanf("%d", &t);
  82.     while (t--)
  83.     {
  84.         int N, Q, type, X, Y;
  85.         LL V;
  86.         scanf("%d %d", &N, &Q);
  87.         build(1, 1, N);
  88.         while(Q--)
  89.         {
  90.             scanf("%d %d %d", &type, &X, &Y);
  91.             if(type==0)
  92.             {
  93.                 scanf("%lld", &V);
  94.                 update(1, 1, N, X, Y, V);
  95.             }
  96.             else
  97.             {
  98.                 printf("%lld", query(1, 1, N, X, Y));
  99.                 putchar_unlocked('\n');
  100.             }
  101.         }
  102.     }
  103.     return 0;
  104. }
Success #stdin #stdout 0s 7524KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/bDQWWm
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!