考点:前缀和+贪心+滑动窗口/单调队列。
可以先叠一个前缀异或,设 S_i=\oplus_{1\le j\le i}a_j,可以 O(n) 预处理 S_i=S_{i-1}\oplus a_i,将问题简化为: \max_{k\le s\le n,s\le r\le n}\min_{r-s+1\le i\le r}S_i 即求所有长为 s(k\le s\le n) (即长至少是 k)的区间 [r-s+1,r],1\le r-s+1,s\le n 里,每个区间最小值的最大值。
观察易得,设 k\le s_1 < s_2\le n,则区间长 s_2 的答案不会比区间长 s_1 的答案更优。因为区间越长,越难让 \min 区间尽可能大。即 k\le s\le n 的最大值必然在 k=s 取得。易证,证略。故问题简化为: \max_{k\le r\le n}\min_{r-k+1\le i\le r}S_i 即求所有长为 k 的区间的最小值的最大值。
不难想到,只需要用滑动窗口维护长为 k 的区间,动态维护最小值即可。因为若存在 S_i \le S_{i-1},则之后的所有区间里,最小值将不再可能从 S_{i-1} 取得而只能在 S_i 取得,因此可以维护单调递增的双端队列即可。
复杂度 O(n)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mn = 2e6 + 10;
ll n, k, ans, s[mn];
signed main()
{
cin.tie(0)->ios::sync_with_stdio(false);
cin >> n >> k;
for (ll i = 1, a; i <= n; ++i)
{
cin >> a;
s[i] = s[i - 1] ^ a;
}
deque<ll> q;
for (ll i = 1; i <= n; ++i)
{
while (!q.empty() && q.front() <= i - k)
{
q.pop_front();
}
while (!q.empty() && s[q.back()] >= s[i])
{
q.pop_back();
}
q.push_back(i);
if (i >= k)
{
ans = max(ans, s[q.front()]);
}
}
cout << ans;
return 0;
}