[ONTAK2015]OR-XOR

题目大意：

一个长度为\(n(n\le5\times10^5)\)的序列\(A(0\le A_i\le10^{18})\)，将其分为恰好\(m\)个连续段，设每一段的代价为这一段数字的异或和，总代价为每一段代价或和。求最小总代价。

思路：

首先求出前缀异或和，答案相当于选出\(m\)个数\(B_{1\sim m}\)，使得\(\vee_{i=1}^{n}B_i\oplus B_{i-1}\)最小。其中\(B_m=A_n\)，\(B_0=0\)。

从高到低按位贪心，某一位可以为\(0\)，当且仅当这\(A_n\)一位为\(0\)，且这一位为\(0\)的数的个数超过\(m\)。如果这一位确实可以为\(0\)，那么就把这一位为\(1\)的数删掉。

源代码：

#include<cstdio>

#include<cctype>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=5e5+1;

int64 a[N];

int main() {

	const int n=getint(),m=getint();

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

		a[i]=a[i-1]^getint();

	}

	int64 ans=0;

	for(register int i=63;i>=0;i--) {

		if(a[n]>>i&1) {

			ans|=1ll<<i;

			continue;

		}

		int cnt=0;

		for(register int j=1;j<=n;j++) {

			if(~a[j]) cnt+=!(a[j]>>i&1);

		}

		if(cnt<m) {

			ans|=1ll<<i;

			continue;

		} else {

			for(register int j=1;j<=n;j++) {

				if((~a[j])&&(a[j]>>i&1)) a[j]=-1;

			}

		}

	}

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

	return 0;

}