fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. long long st[int(8e5)], lz[int(8e5)];
  4. long long cons(int i, int l, int r, int a[]){
  5. 	lz[i] = -1;
  6. 	if(l == r){
  7. 		return st[i] = 1LL << a[l];
  8. 	}
  9. 	int mid = (l+r)/2;
  10. 	return st[i] = cons(i*2, l, mid, a) | cons(i*2+1, mid+1, r, a);
  11. }
  12. void prop(int i, int l, int r){
  13. 	if(lz[i] == -1) return;
  14. 	st[i] = lz[i];
  15. 	if(l != r){
  16. 		lz[i*2] = lz[i];
  17. 		lz[i*2+1] = lz[i];
  18. 	}
  19. 	lz[i] = -1;
  20. }
  21. long long get(int i, int l, int r, int a, int b){
  22. 	prop(i, l, r);
  23. 	if(b < l || r < a) return 0;
  24. 	if(a <= l && r <= b) return st[i];
  25. 	int mid = (l+r)/2;
  26. 	return get(i*2, l, mid, a, b) | get(i*2+1, mid+1, r, a, b);
  27. }
  28. void upd(int i, int l, int r, int a, int b, int v){
  29. 	prop(i, l, r);
  30. 	if(b < l || r < a) return;
  31. 	if(a <= l && r <= b) {
  32. 		st[i] = 1LL << v;
  33. 		if(l != r){
  34. 			lz[i*2+1] = lz[i*2] = 1LL << v;
  35. 		}
  36. 		return;
  37. 	}
  38. 	int mid = (l+r)/2;
  39. 	upd(i*2, l, mid, a, b, v);
  40. 	upd(i*2+1, mid+1, r, a, b, v);
  41. 	st[i] = st[i*2] | st[i*2+1];
  42. }
  43. int main(){
  44. 	ios_base::sync_with_stdio(false);
  45. 	cin.tie(NULL);
  46. 	int n, q, t, l, r, v;
  47. 	cin >> n >> q;
  48. 	int a[n];
  49. 	for(int i = 0;i < n;i++) cin >> a[i];
  50. 	cons(1, 0, n-1, a);
  51. 	while(q--){
  52. 		cin >> t;
  53. 		if(t == 1){
  54. 			cin >> l >> r >> v;
  55. 			upd(1, 0, n-1, l-1, r-1, v);
  56. 		} else {
  57. 			cin >> l >> r;
  58. 			cout << __builtin_popcountll(get(1, 0, n-1, l-1, r-1)) << '\n';
  59. 		}
  60. 	}
  61. }
Success #stdin #stdout 0s 5532KB
comments (?)
stdin
copy 
5 5
1 1 1 1 1
1 2 4 2
1 5 5 3
2 1 5
2 1 4
2 2 4
stdout
copy 
3
2
1
https://ideone.com/vEcpw0
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!