考虑把原问题写成一个在 (\left(\log_2 \max v \right) \times n) 的矩阵里选出三列，我们首先预处理出 (j \cap q)。具体，我们需要对于每一个权值 (v) 求出一个最大的下标 (p)（(1 \leqslant p \leqslant n)）满足存在极大的 (q < p) 且 (v \cap a_p \cap a_q = v)，即 (v \subseteq \left(a_p \cap a_q\right))，这个可以做一个二元组 dp，即设 (f_v) 为对于 (v) 而言的答案，注意到 (p) 和 (q) 的实际意义是「满足左右两边存在有一个位置做并操作后是 (v) 的超集的位置下标」的最大值和次大值，所以更新答案是容易的。
考虑如何转移。对于一个左闭右开区间 ([0, 2^n))，我们分治求出 ([0, 2^{n-1})) 和 ([2^{n-1}, 2^n)) 的 dp，当然左边区间的 dp 值不会对右边区间产生影响，所以我们考虑右边区间对左边区间的影响。(\forall i \in [l, m))，我们需要从 (i) 的超集转移到 (i)，因为在 dp 时我们实际上是把所有贡献放到一个点上，又注意到 (i-l+m) 和 (i) 的关系就是二进制意义下多了一个最高位的 (1)，所以只需要从 (i-l+m) 转移到 (i) 即可（有点谜语，但就这样吧）。
然后就贪心取最高位，挨个取 max 就行了。
int n, a[1000100], qwq;
pii dp[3000100];
pii upd(const pii& x, const pii& y) {
if (x.first > y.first) {
return pii(x.first, max(y.first, x.second));
}
else {
return pii(y.first, max(x.first, y.second));
}
}
void sos_dp(int l, int r) {
if (r-l == 1) {
return;
}
int mid = (l+r)/2;
sos_dp(l, mid), sos_dp(mid, r);
for (int i=l; i> n;
for (int i=1; i> a[i];
dp[a[i]] = upd(dp[a[i]], pii(i, 0));
}
qwq = 1;
for (int up=*max_element(a+1, a+n+1); (1<=0; --j) {
if (~(a[i]>>j)&1 && dp[offset|(1< i) {
offset |= 1< i) {
f = 1;
}
if (f) {
cmax(ans, a[i]|offset);
}
}
cout << ans << "\n";
}
Original: https://www.cnblogs.com/orchid-any/p/16543332.html
Author: BoringHacker
Title: 「codeforces-1208F」Bits and Pieces
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604058/
转载文章受原作者版权保护。转载请注明原作者出处！