fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define F first
  5. #define S second
  6. #define int long long
  7. #define Ali ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
  8.  
  9. const int N = 5e5 + 7;
  10. const int MOD = 1e9 + 7;
  11. int t[N][23], a[N], p[N][23];
  12.  
  13. void build(int v, int l, int r, int bit){
  14. 	if (l == r){
  15. 		t[v][bit] = (a[l] >> bit) & 1;
  16. 		return;
  17. 	}
  18. 	int mid = (l + r) / 2;
  19. 	build(v * 2, l, mid, bit);
  20. 	build(v * 2 + 1, mid + 1, r, bit);
  21. 	t[v][bit] = t[v * 2][bit] + t[v * 2 + 1][bit];
  22. }
  23.  
  24. void push(int v, int l, int r, int bit){
  25. 	if (p[v][bit] && l != r){
  26. 		int mid = (r + l) / 2;
  27. 		p[v * 2][bit] ^= 1;
  28. 		p[v * 2 + 1][bit] ^= 1;
  29. 		t[v * 2][bit] = mid - l + 1 - t[v * 2][bit];
  30. 		t[v * 2 + 1][bit] = r - mid - t[v * 2 + 1][bit];
  31. 		p[v][bit] = 0;
  32. 	}
  33. }
  34.  
  35. void upd(int v, int l, int r, int tl, int tr, int bit){
  36. 	if (l > tr || r < tl) return;
  37. 	if (tl <= l && r <= tr){
  38. 		t[v][bit] = r - l + 1 - t[v][bit];
  39. 		p[v][bit] ^= 1;
  40. 		return;
  41. 	}
  42. 	push(v, l, r, bit);
  43. 	int mid = (l + r) / 2;
  44. 	upd(v * 2, l, mid, tl, tr, bit);
  45. 	upd(v * 2 + 1, mid + 1, r, tl, tr, bit);
  46. 	t[v][bit] = t[v * 2][bit] + t[v * 2 + 1][bit];
  47. }
  48.  
  49. int get(int v, int l, int r, int tl, int tr, int bit){
  50. 	push(v, l, r, bit);
  51. 	if (l > tr || r < tl) return 0;
  52. 	if (tl <= l && r <= tr) return t[v][bit];
  53. 	int mid = (r + l) / 2;
  54. 	return get(v * 2, l, mid, tl, tr, bit) + get(v * 2 + 1, mid + 1, r, tl, tr, bit);
  55. }
  56.  
  57. void abb() {
  58. 	int n;
  59. 	cin >> n;
  60. 	for (int i = 1; i <= n; ++i){
  61. 		cin >> a[i];
  62. 	}for (int i = 0; i <= 20; ++i) build(1, 1, n, i);
  63. 	int q; cin >> q;
  64. 	for (int i = 1; i <= q; ++i){
  65. 		int type, l, r;
  66. 		cin >> type >> l >> r;
  67. 		if (type == 1){
  68. 			int sum = 0;
  69. 			for (int j = 0; j <= 20; ++j) sum += (get(1, 1, n, l, r, j) * (1ll << j));
  70. 			cout << sum << '\n';
  71. 		}else{
  72. 			int x; cin >> x;
  73. 			for (int j = 0; j <= 20; ++j){
  74. 				if (x & (1ll << j)) upd(1, 1, n, l, r, j);
  75. 			}
  76. 		}
  77. 	}
  78. }
  79. signed main(){
  80.     Ali;
  81.     int T = 1;
  82. //    cin >> T;
  83.     while(T--){
  84.         abb();
  85.     }
  86. }
Time limit exceeded #stdin #stdout 5s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FiMb2o
language:
C++ (gcc 8.3)
created:
1 year 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!