题意

给定一个长度为 $n$ 的非负整数序列 $[a_1,…,a_n]$ ，求它的一个子序列 $[{a_i}_1,{a_i}_2,…,{a_i}_k]$ $(1≤i_1<i_2<⋯<i_k≤n)$ ，使得 $\sum^{k−1}_{j=1}({a_i}_j\text{and} {a_i}_{j+1})$ 最大。你只需要输出这个最大值即可。

$n\leq2\times10^5,0\leq a_i\leq10^{12}$ 。

题解

挺简单的题，但思考的时间还是太长了。

一个显然的 $\mathcal{O}(n^2)$ ： $f_i=\max_{j<i}\{f_j+(a_i~\text{and}~a_j)\}$ ，考虑优化。这个与的二进制位的操作，让我想到类似树状数组的操作。对于 $i$ ，它选择 $j$ 的“权重”，是尽量选 $a_i~\text{and}~a_j$ 二进制最高位大的，且 $f_i$ 要大。那么对每个二进制位，维护它目前最大 $f$ ，之后的 $i$ ，如果这一位有 1 就试着选它。正确性很容易证：当前 $f$ 在第 $\text{bit}$ 位比目前最大的 $f$ 要大，那么它肯定要大 $\Omega(2^\text{bit})$ 的数量级，因为如果不如这个大，那么当前 $f$ 应该选择目前最大 $f$ 。

复杂度 $\mathcal{O}(n\log A)$ ，其中 $A$ 是 $a_i$ 的值域。注意考虑 $a_i~\text{and}~a_j=0$ （即全局最大）的情况。

代码

const int N = 1e6 + 5, M = 42;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	ll a[N], f[N], ans;
	struct node{ 
		ll val, a;
	} mx[M], nop;
	int main() {
		n = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i <= n; i++) {
			f[i] = max(f[i], nop.val + (nop.a & a[i]));
			for (int j = 40; ~j; --j) {
				if ((a[i] >> j) & 1) {
					f[i] = max(f[i], mx[j].val + (mx[j].a & a[i]));
				}
			}
			for (int j = 40; ~j; --j) {
				if ((a[i] >> j) & 1) {
					if (mx[j].val <= f[i]) mx[j] = (node) {f[i], a[i]};
				}
			}
			if (nop.val <= f[i]) nop = (node) {f[i], a[i]};
			ans = max(ans, f[i]);
		}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main() {
//	freopen("ex_seq4.in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}