1902. 01trie上动态点分治

考点:前缀和+贪心+滑动窗口/单调队列。

可以先叠一个前缀异或,设 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; }