fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5.  
  6.  
  7.  
  8. int n, type, l, r, x, lazy[4 * N];
  9. long long t[4 * N];
  10.  
  11. inline void push(int v, int l, int r){
  12. 	if(lazy[v] == -1){
  13. 		// so there's no lazy
  14. 		return;
  15. 	}
  16. 	lazy[v + v] = lazy[v + v + 1] = lazy[v];
  17. 	int mid = (r + l) >> 1;
  18. 	t[v + v] = 1ll * lazy[v] * (mid - l + 1);
  19. 	t[v + v + 1] = 1ll * lazy[v] * (r - mid);
  20. 	// we did all propagations
  21. 	lazy[v] = -1;
  22. }
  23.  
  24. void update(int v, int l, int r, int tl, int tr, int val){
  25. 	if(l > r || l > tr || tl > r){
  26. 		return;
  27. 	}
  28. 	if(tl <= l && r <= tr){
  29. 		t[v] = 1ll * val * (r - l + 1);
  30. 		lazy[v] = val;
  31. 		return;
  32. 	}
  33. 	push(v, l, r);
  34. 	int mid = (r + l) >> 1;
  35. 	update(v + v, l, mid, tl, tr, val);
  36. 	update(v + v + 1, mid + 1, r, tl, tr, val);
  37. 	t[v] = t[v + v] + t[v + v + 1];
  38. }
  39.  
  40. long long get(int v, int l, int r, int tl, int tr){
  41. 	if(l > r || l > tr || tl > r){
  42. 		return 0;
  43. 	}
  44. 	if(tl <= l && r <= tr){
  45. 		return t[v];
  46. 	}
  47. 	push(v, l, r);
  48. 	int mid = (r + l) >> 1;
  49. 	return get(v + v, l, mid, tl, tr) + get(v + v + 1, mid + 1, r, tl, tr);
  50. }
  51.  
  52. int main(){
  53. 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  54. 	cin >> n;
  55. 	// set lazy -1
  56. 	memset(lazy,-1,sizeof(lazy));
  57. 	for(int i = 1; i <= n; i++){
  58. 		cin >> type >> l >> r;
  59. 		if(type == 1){
  60. 			cin >> x;
  61. 			update(1, 1, n, l, r, x);
  62. 		}
  63. 		else{
  64. 			cout << get(1, 1, n, l, r) << "\n";
  65. 		}
  66. 	}
  67. }
Success #stdin #stdout 0s 19928KB
comments (?)
stdin 
5
1 2 3 4
2 2 2
1 1 1 5
2 1 3
2 2 3
stdout 
4
13
8
https://ideone.com/kQ0AKa
language:
C++14 (gcc 8.3)
created:
6 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!