Codeforcs 1732C2 暴力

题意

传送门 Codeforcs 1732C2

题解

方便起见，区间表示为左闭右开。观察到 $f(l,r)\ge f(l^{\prime },r^{\prime }),[l^{\prime },r^{\prime })\in [l,r)$，满足单调性，则 $[l,r)$ 子区间最大 $f$ 等于 $f(l,r)$。当同一数位出现大于一次 $1$ 时，这一数对 $f$ 的贡献大于 $0$，那么暴力枚举左右边界即可。时间复杂度 $O(q{\log }^2(\max a_i))$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt;cin >> tt;while (tt--) {int n, q;cin >> n >> q;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}vector<ll> sum(n + 1);vector<int> xsum(n + 1);for (int i = 0; i < n; ++i) {sum[i + 1] = sum[i] + a[i];xsum[i + 1] = xsum[i] ^ a[i];}vector<int> pos;for (int i = 0; i < n; ++i) {if (a[i] != 0) {pos.push_back(i);}}while (q--) {int l, r;cin >> l >> r;l -= 1;ll x = (sum[r] - sum[l]) - (xsum[r] ^ xsum[l]);if (x == 0) {cout << l + 1 << ' ' << l + 1 << '\n';continue;}int mn = r - l;int ml = l, mr = r;int lb = lower_bound(pos.begin(), pos.end(), l) - pos.begin();int ub = lower_bound(pos.begin(), pos.end(), r) - pos.begin();for (int i = lb; i < ub && i < lb + 31; ++i) {for (int j = ub - 1; j >= i && j >= ub - 32; --j) {ll s = sum[pos[i]] - sum[l] + sum[r] - sum[pos[j] + 1];int xs = xsum[pos[i]] ^ xsum[l] ^ xsum[r] ^ xsum[pos[j] + 1];if ((sum[r] - sum[l] - s) - (xsum[r] ^ xsum[l] ^ xs) == x) {if (pos[j] + 1 - pos[i] < mn) {ml = pos[i];mr = pos[j] + 1;mn = mr - ml;}}}}cout << ml + 1 << ' ' << mr << '\n';}}return 0;
}