Sheikh (Easy version)

发表于 分类于 ，

    给出一个数组a，长度为n。

    定义$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$，$\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$，$\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$。

    求最大f值的子数组。

    $n\le 10^5$

Sheikh (Easy version)

Created by LXC on Fri Jul 28 10:55:36 2023

https://codeforces.com/problemset/problem/1732/C1

ranting: 1800

tag: binary search, bitmasks, greedy, two pointers

problem

给出一个数组a，长度为n。
定义$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$，$\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$，$\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$。

求最大f值的子数组。

$n\le 10^5$

solution

核心规律$f(l, r) \leq f(l, r + 1)$，区间长度越大f不会减小。存在区间包含的单调性，可以用二分或双指针。

code

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102


#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    int L, R;
    cin >> L >> R;
    int mn = n + 1;
    vector<ll> suf_sm(n + 1, 0), suf_xr(n + 1, 0);
    ll sm = 0, xr = 0;
    ll mx = 0;
    for (int i = n - 1; i >= 0; i--) {
        sm += a[i];
        xr ^= a[i];
        suf_sm[i] = sm;
        suf_xr[i] = xr;
        mx = max(mx, sm - xr);
    }
    for (int i = 0; i < n; i++) {
        if (mx != sm - xr)
            continue;
        int l = i + 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            // ll tsm = 0, txr = 0;
            // for (int j = i; j < m; j++) {
            //     tsm += a[j];
            //     txr ^= a[j];
            // }
            ll tsm = sm - suf_sm[m], txr = xr ^ suf_xr[m];
            if (tsm - txr == mx) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        if (mn > r - i) {
            L = i + 1;
            R = r;
            mn = r - i;
        }
        sm -= a[i];
        xr ^= a[i];
    }
    cout << L << " " << R << endl;
}

void sol2() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n + 1), sm(n + 1), xr(n + 1);
    ll mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sm[i] = sm[i - 1] + a[i];
        xr[i] = xr[i - 1] ^ a[i];
        mx = max(mx, sm[i] - xr[i]);
    }
    int L, R;
    cin >> L >> R;
    for (int i = 1, j = 1; i <= n; i++) {
        j = max(i, j);
        while (j <= n && sm[j] - sm[i - 1] - (xr[j] ^ xr[i - 1]) < mx)
            j++;
        if (j > n)
            break;
        if (j - i < R - L) {
            R = j, L = i;
        }
    }
    cout << L << " " << R << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        // sol();
        sol2();
    }
#else
    sol();
#endif
    return 0;
}