fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. // Функция для вычисления XOR всех элементов до индекса k
  8. int computePrefixXOR(const vector<int>& prefixXOR, long long k) {
  9.     if (k == 0) return 0;
  10.     if (k > prefixXOR.size()) return prefixXOR.back();
  11.     return prefixXOR[k - 1];
  12. }
  13.  
  14. // Рекурсивная функция с мемоизацией для вычисления a_m
  15. int computeA(long long m, const vector<int>& prefixXOR, unordered_map<long long, int>& memo) {
  16.     if (memo.count(m)) return memo[m]; // Если значение уже вычислено, возвращаем его
  17.     if (m <= prefixXOR.size()) return prefixXOR[m - 1]; // Если m <= n, возвращаем a_m
  18.     long long half = m / 2;
  19.     int result = computeA(half, prefixXOR, memo); // Рекурсивно вычисляем a_{m/2}
  20.     memo[m] = result; // Сохраняем результат в мемоизацию
  21.     return result;
  22. }
  23.  
  24. int main() {
  25.     int t;
  26.     cin >> t;
  27.  
  28.     while (t--) {
  29.         int n;
  30.         long long l, r;
  31.         cin >> n >> l >> r;
  32.  
  33.         vector<int> a(n);
  34.         for (int i = 0; i < n; ++i) {
  35.             cin >> a[i];
  36.         }
  37.  
  38.         // Вычисляем префиксный XOR
  39.         vector<int> prefixXOR(n);
  40.         prefixXOR[0] = a[0];
  41.         for (int i = 1; i < n; ++i) {
  42.             prefixXOR[i] = prefixXOR[i - 1] ^ a[i];
  43.         }
  44.  
  45.         // Мемоизация для хранения уже вычисленных значений a_m
  46.         unordered_map<long long, int> memo;
  47.  
  48.         // Вычисляем a_l
  49.         int result = computeA(l, prefixXOR, memo);
  50.  
  51.         // Выводим результат
  52.         cout << result << endl;
  53.     }
  54.  
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
12 69 69
1 0 0 0 0 1 0 1 0 1 1 0
stdout
copy 
1
https://ideone.com/n8syeX
language:
C++14 (gcc 8.3)
created:
9 days 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!