fork download 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 2e4 + 5;
  38. const int S = 100;
  39. int n, q, a[N], pref[N];
  40. int rmq[15][N / S + 5][N], dp[N / S + 5][S + 2][S + 2];
  41.  
  42. struct Node {
  43.     Node *child[2];
  44.     int cnt;
  45.  
  46.     Node() {
  47.         child[0] = child[1] = NULL;
  48.         cnt = 0;
  49.     }
  50. } *root;
  51.  
  52. void update(int x, int sign) {
  53.     Node* p = root;
  54.     RED(i, 30) {
  55.         int pos = BIT(x, i);
  56.         if (p -> child[pos] == NULL) p -> child[pos] = new Node();
  57.         p = p -> child[pos];
  58.         p -> cnt += sign;
  59.     }
  60. }
  61.  
  62. int getXor(int x) {
  63.     Node* p = root;
  64.     int ans = 0;
  65.     RED(i, 30) {
  66.         int pos = BIT(x, i);
  67.         if (p -> child[pos ^ 1] != NULL && p -> child[pos ^ 1] -> cnt > 0) {
  68.             p = p -> child[pos ^ 1];
  69.             ans |= MASK(i);
  70.         } else if (p -> child[pos] != NULL && p -> child[pos] -> cnt > 0) {
  71.             p = p -> child[pos];
  72.         }
  73.     }
  74.     return ans;
  75. }
  76.  
  77. void init(void) {
  78.     cin >> n >> q;
  79.     REP(i, n) {
  80.         cin >> a[i];
  81.         if (i > 0) pref[i] = pref[i - 1] ^ a[i];
  82.         else pref[i] = a[i];
  83.     }
  84. }
  85.  
  86. void process(void) {
  87.     root = new Node();
  88.     for(int B = 0; B < n; B += S) {
  89.         int R = min(n, B + S) - 1;
  90.         int block = B / S;
  91.         FOR(i, B, R) update(pref[i], +1);
  92.         REP(i, R) {
  93.             rmq[0][block][i] = getXor((!i ? 0 : pref[i - 1]));
  94.             if (B <= i && i <= R) update(pref[i], -1);
  95.         }
  96.         update(pref[R], -1);
  97.  
  98.         FOR(i, B - 1, R - 1) update((i == -1 ? 0 : pref[i]), +1);
  99.         FOR(i, R, n - 1) rmq[0][block][i] = getXor(pref[i]);
  100.         FOR(i, B - 1, R - 1) update((i == -1 ? 0 : pref[i]), -1);
  101.  
  102.         FORR(l, R, B) {
  103.             dp[block][l - B][l - B] = a[l];
  104.             FOR(r, l + 1, R)
  105.                 dp[block][l - B][r - B] = max({dp[block][l - B][r - B - 1],
  106.                                                       dp[block][l + 1 - B][r - B], pref[r] ^ (!l ? 0 : pref[l - 1])});
  107.         }
  108.     }
  109.  
  110.     FOR(j, 1, 14) FOR(B, 0, n / S) REP(i, n - MASK(j) + 1)
  111.         rmq[j][B][i] = max(rmq[j - 1][B][i], rmq[j - 1][B][i + MASK(j - 1)]);
  112.  
  113.  
  114.     auto get_max = [&](const int B, int l, int r) {
  115.         int k = __lg(r - l + 1);
  116.         return max(rmq[k][B][l], rmq[k][B][r - MASK(k) + 1]);
  117.     };
  118.  
  119.     int l, r, last_ans = 0;
  120.  
  121.     FOR(i, 1, q) {
  122.         cin >> l >> r;
  123.         l = (l + last_ans) % n;
  124.         r = (r + last_ans) % n;
  125.         if (l > r) swap(l, r);
  126.  
  127.         int blockL = (l + S - 1) / S;
  128.         int blockR = r / S;
  129.  
  130.         int ans = 0;
  131.         if (blockL >= blockR) {
  132.             if (l / S == r / S) {
  133.                 cout << (last_ans = dp[l / S][l - (l / S) * S][r - (r / S) * S]) << '\n';
  134.                 continue;
  135.             }
  136.             FOR(i, l, r) {
  137.                 update((i == -1 ? 0 : pref[i - 1]), +1);
  138.                 maximize(ans, getXor(pref[i]));
  139.             }
  140.             FOR(i, l - 1, r - 1) update((i == -1 ? 0 : pref[i]), -1);
  141.             cout << (last_ans = ans) << '\n';
  142.             continue;
  143.         }
  144.  
  145.         maximize(ans, dp[l / S][l - (l / S) * S][S - 1]);
  146.         FOR(B, blockL, blockR - 1) maximize(ans, get_max(B, l, r));
  147.         maximize(ans, dp[r / S][0][r - (r / S) * S]);
  148.  
  149.         FOR(i, l - 1, blockL * S) update((i == -1 ? 0 : pref[i]), +1);
  150.         FOR(i, blockR * S, r) maximize(ans, getXor(pref[i]));
  151.         cout << (last_ans = ans) << '\n';
  152.  
  153.         FOR(i, l - 1, blockL * S) update((i == -1 ? 0 : pref[i]), -1);
  154.     }
  155. }
  156.  
  157. int main() {
  158.     ios_base::sync_with_stdio(0);
  159.     cin.tie(0); cout.tie(0);
  160.     if (fopen(task".inp", "r")) {
  161.         freopen(task".inp", "r", stdin);
  162. //        freopen(task".out", "w", stdout);
  163.     }
  164.     int tc = 1;
  165. //     cin >> tc;
  166.     while(tc--) {
  167.         init();
  168.         process();
  169.     }
  170.     return 0;
  171. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hFzf5H
language:
C++14 (gcc 8.3)
created:
2 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!