stillnotred

Untitled

Feb 28th, 2025
289
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 1e6 + 10;
  5.  
  6. void solve() {
  7.     int n,l,r;
  8.     cin >> n >> l >> r;
  9.     // re
  10.     vector<int> v(n + 1);
  11.     for (int i = 1; i <= n; i++) {
  12.         cin >> v[i];
  13.     }
  14.  
  15.     map<int, int> dp;
  16.     dp[0] = 0;
  17.     dp[1] = dp[2] = dp[3] = v[1];
  18.  
  19.     for (int i = 4; i <= n; i++) {
  20.         dp[i] = dp[i - 2] ^ v[i / 2];
  21.     }
  22.  
  23.     // cout << "as";
  24.     // return ;
  25.  
  26.     function<int(int)> fun = [&](int x) {
  27.         if(x <= 0){
  28.             return 0ll;
  29.         }
  30.         if (dp.count(x)){
  31.             return dp[x];
  32.         }
  33.         return dp[x] = fun(x - 2) ^ fun(x / 2);
  34.     };
  35.  
  36.     cout << fun(l);
  37. }
  38.  
  39. int32_t main() {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(NULL);
  42.  
  43.     int t;
  44.     cin >> t;
  45.     while (t--) {
  46.         solve();
  47.         cout << '\n';
  48.     }
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment