Description：

给定一个长度为 $n$ 的序列 $a[1],a[2],\dots,a[n]$ ，请将它划分为 $m$ 段连续的区间，设第 $i$ 段的费用 $c[i]$ 为该段内所有数字的异或和，则总费用为 $c[1] \text{ or } c[2] \text{ or } \dots \text{ or } c[m]$ 。请求出总费用的最小值。

$1\le n \le 500000$

Solution：

类似于巴厘岛的雕塑，从高到低按位贪心，依次判断是否存在一个满足之前所有位的这一位为 $0$ 的方案。先求出所有数的异或前缀和，那么如果有 $\ge m$ 个前缀和这一位为 $0$ ，并且最后一个前缀和可以用且这一位为 $0$ ，那么在最终答案中这一位可以为 $0$ ，这就说明所有前缀和这一位为 $1$ 的位置都不可选，打个标记即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

typedef long long ll;

ll a[MAXN],s[MAXN];

bool tag[MAXN];

int main()

{

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

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

	for(int i = 1;i <= n;++i)s[i] = s[i - 1] ^ a[i];

	memset(tag,false,sizeof(tag));

	ll ans = 0;

	for(int b = 62;b >= 0;--b)

	{

		int cnt = 0;

		for(int i = 1;i <= n;++i)

			if(!tag[i] && (s[i] & (1ll << b)) == 0)

				++cnt;

		if(cnt >= m && !tag[n] && (s[n] & (1ll << b)) == 0)

		{

			for(int i = 1;i <= n;++i)

			{

				if(!tag[i] && (s[i] & (1ll << b)) != 0)

				{

					tag[i] = true;

				}

			}

		}

		else ans |= (1ll << b);

	}

	cout << ans << endl;

	return 0;

}