时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目描述

Nichika 得到了一组序列 $a_n$ ，她想把这个序列划分成 $k$ 段，每段至少包含一个元素，每个元素都属于某个段。

Mikoto 把每一段的价值定义为该段内所有元素的按位或，将整个序列的价值定义为所有段价值的按位与。

Nichika 想要得到尽可能高的价值，请你帮助她算出来她能获得的最大序列价值。

# 输入格式

第一行两个整数 $n, k$ ，表示序列长度和需要划分的段数。( $1 \le k \le n \le 2 \times 10^5$ )

第二行 $n$ 个整数，第 $i$ 个为 $a_i$ ，表示 Nichika 得到的序列。( $0 \le a_i < 2^{30}$ )

# 输出格式

一行一个整数，表示将序列分成 $k$ 段后能得到的最大序列价值。

# 输入样例

	5 3
	2 1 2 3 1

# 输出样例

# 样例解释

能取到最大值的一种划分是 | 2 1 | 2 |3 1 | ，得到答案为 $3 \& 2 \& 3 = 2$ 。

# 题解：位运算 + 贪心

由于位运算对每一位具有独立性，我们将每一位拆开来分别考虑。

要求将序列分成 $k$ 段后能得到的最大序列价值，考虑一种贪心的思路，尽量使更高的位能凑出 $1$ ，这样下来得到的价值一定是最大的。

同时我们还发现，如果我们存在一种方式，将序列分为 $k + 1$ 段，使得价值为 $w$ ，那么一定有一种方式将序列分为 $k$ 段，使得价值能不低于 $w$ ，因为我们将任意两个相邻段合并，减少了与运算，增加了或运算，最终结果会增大。

于是我们从最高位依次向最低位考虑，记录下当前位为 $1$ 的所有数的位置，综合之前更高位记录下的位置，我们要考虑将 $n$ 个数分为 $k$ 段，使每一段内，每一位至少包含一个 $1$ ，如果加入当前位后能实现这一点，那么我们答案的这一位就能填 $1$ ；否则，我们答案的这一位不能填 $1$ ，同时我们丢弃当前这一位记录下的所有数的位置（因为后续不需要再满足这一位填 $1$ ）。比较抽象，建议直接看代码实现。

时间复杂度为 $O(n \log^2 a)$ 。

参考代码：

	#include <stdio.h>
	#include <stdbool.h>
	#include <string.h>

	int n, k, group, ans, a[200010], cnt[30], ind[30], pos[30][200010];

	static inline int max(int a, int b)
	{
	return (a > b) ? a : b;
	}

	static inline bool Check()
	{
	memset(ind, 0, sizeof(ind)); //ind 是一个下标数组，初始都指向第 0 位

	for (int i = 1; i <= k; ++ i)
	{
	int maxPos = 0; // 记录下一次划分划到什么位置，我们要保证每一位都至少出现一个 1，所以取最远的那一位

	for (int j = 1; j <= group; ++ j)
	{
	if (ind[j] == cnt[j]) // 还没划分出 k 段，已经有某一位划分不下去了，划分失败
	return false;

	maxPos = max(maxPos, pos[j][ind[j] + 1]);
	}

	for (int j = 1; j <= group; ++ j)
	while (ind[j] < cnt[j] && pos[j][ind[j] + 1] <= maxPos) // 每一位都至少移到这个位置之前
	++ ind[j];
	}

	return true;
	}

	int main()
	{
	// freopen("B.in", "r", stdin);
	// freopen("B.out", "w", stdout);

	scanf("%d%d", &n, &k);

	for (int i = 1; i <= n; ++ i)
	scanf("%d", &a[i]);

	for (int i = 29; ~i; -- i)
	{
	++ group; // 先加入这一位，后续再看能不能满足
	cnt[group] = 0;

	for (int j = 1; j <= n; ++ j)
	if (a[j] >> i & 1)
	pos[group][ ++ cnt[group]] = j;

	if (cnt[group] < k) // 这一位为 1 的数都小于 k 个，肯定划分不出来
	-- group; // 减掉这一组
	else if (Check())
	ans \|= 1 << i; // 加入这一位可以实现，我们就让答案的这一位为 1，同时不执行 -- group，因为我们要保留下这一组的数据，为了后续判定是否能划分
	else
	-- group; // 同上
	}

	printf("%d\n", ans);

	return 0;
	}

位运算贪心