1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| #include <iostream> #include <cstdio> #include <queue> #include <algorithm> #define maxn 1000010 #define INF 1000000000 #define ll long long #define lowbit(i) ((i) & (-i)) using namespace std; int n, m;
ll a[maxn];
ll mx[maxn], mn[maxn], v[maxn], ans, w[maxn], W[maxn], M; void solve(int l, int r) { if (l == r) return (void) (ans ^= a[l]); int m = l + r >> 1, cx = m, cn = m; mn[m + 1] = mx[m + 1] = a[m + 1]; mn[m] = mx[m] = a[m]; w[m] = W[m] = v[m] = 0; W[m + 1] = w[m + 1] = v[m + 1] = a[m + 1]; for (int i = m + 2; i <= r; ++i) { mn[i] = min(a[i], mn[i - 1]); mx[i] = max(a[i], mx[i - 1]); v[i] = v[i - 1] ^ (mx[i] | mn[i]); w[i] = w[i - 1] ^ mx[i]; W[i] = W[i - 1] ^ mn[i]; } for (int i = m; i >= l; --i) { while (cx < r && mx[cx + 1] <= mx[i]) ++cx; while (cn < r && mn[cn + 1] >= mn[i]) ++cn; ans ^= (min(cx, cn) - m & 1) * (mn[i] | mx[i]); if (cx < cn) { ll v = w[cn] ^ w[cx]; if (cn - cx & 1) v |= mn[i]; else v &= M ^ mn[i]; ans ^= v; } else if (cx > cn) { ll v = W[cx] ^ W[cn]; if (cx - cn & 1) v |= mx[i]; else v &= M ^ mx[i]; ans ^= v; } ans ^= v[r] ^ v[max(cn, cx)]; mx[i - 1] = max(mx[i], a[i - 1]); mn[i - 1] = min(mn[i], a[i - 1]); } solve(l, m); solve(m + 1, r); }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n; M = (1ll << 60) - 1; for (int i = 1; i <= n; ++i) cin >> a[i]; solve(1, n); cout << ans << "\n"; return 0; }
|