题目
给定数列(a),求(a_i|(a_j & a_k))的最大值,其中(i<j<k)。
题解
很容易想到预先处理(a_j & a_k)。由于(a)的值域为(2 imes 10^{6}),所以可以求出每个数的是否能被与表示出来。对于某个值(i),如果有(i=j&k),那么必有(iin j)以及(i in k),这里(in)的意思是将二进制的1看作集合的元素时的属于关系。所以就是找每个数(i)的超集。事实上,真正想要的是所有(i)的超集中最靠后的两个位置,因为还要或一个数,所以越靠后越优。
即求(P(i)=maxlimits_{i in j}(p(j))),(p(j))代表(j)所在的位置。这个可以用fwt的思想,分治的方法解决(好像也叫作SOSdp)。
处理完后,对于每个(a_i),从高位到低位遍历,贪心地看能不能在这一位或上1。假设当前位(p)可以或上1,那么当前或操作的贡献为(d=d|(2^p)),如果(P(d|(2^p))>i),说明存在(a_j&a_k)可以使得(a_i)或上这个1。最后(a_i)的最大值为(a_i|d)。
时间复杂度(O((n+M)log M)),(M)为值域。
注意事项:
-
可能有不存在(a_j& a_k)使得(a_i)变大情况,此时不要算上(a_i|d)的贡献。否则就会
Wrong answer on test 139
-
预处理部分(dp)计算没有前后依赖关系,不要写成cdq分治了,即正确写法是算左算右再合并,而不是算右、算右对左的贡献、算左,否则会有重复贡献。
-
预处理后的步骤想反了,居然想遍历(a_j& a_k),找(a_i)。太笨了。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 3e6 + 10;
const double eps = 1e-5;
typedef pair<int, int> PII;
PII dp[N];
PII upd(const PII& a, const PII& b) {
int ra, rb;
if(a.first > b.first) {
return {a.first, max(a.second, b.first)};
} else {
return {b.first, max(b.second, a.first)};
}
}
void solve(int l, int r) {
if(l == r) return ;
int mid = (l + r) / 2;
solve(l, mid);
solve(mid + 1, r);
for(int i = l; i <= mid; i++) {
dp[i] = upd(dp[i], dp[i - l + mid + 1]);
}
}
int get(int x) {
int len = 1;
while((1 << len) <= x) {
len++;
}
return len;
}
int arr[N];
int main() {
IOS;
int n, len = 0, mx = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
dp[arr[i]] = upd(dp[arr[i]], {i, 0});
mx = max(mx, arr[i]);
}
len = get(mx);
mx = (1 << len);
solve(0, mx - 1);
int ans = 0;
for(int i = 1; i <= n; i++) {
int d = 0;
bool ok = false;
for(int j = len - 1; j >= 0; j--) {
if(!(arr[i] & (1 << j))) {
if(dp[d | (1 << j)].second > i) {
d |= (1 << j);
ok = true;
}
}
}
if(dp[d].second > i) {
ok = true;
}
if(ok) ans = max(ans, arr[i] | d);
}
cout << ans << endl;
}