题意:一个长度为$n$的序列,要划分为$m$个区间,每个区间的花费是区间内的异或和,总花费是$m$个区间花费的$or$,求最小花费
------------
首先求出异或前缀和$b$
第$i$个区间的花费就是$b[r[i]]xorb[r[i-1]]$,其中$r[i]$表示区间右端点
考虑最小化总花费
从高位到低位贪心,尽量使当前这一位为$0$
某一位可以为$0$的条件是:$b$数组中这一位为$0$的数的个数不少于$m$个且$b[n]$的这一位为$0$
如果这一位可以为$0$,那么这一位为$1$的位置都不能作为区间右端点
注意位运算的时候要加$ll$
这里判断某一位是否为$1$的时候只能用这种写法
不能把$b[i]$右移$j$位,否则会$WA$
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=5e5+5;
int n,m;
ll b[N],ans;
bool vis[N];
inline ll read()
{
ll x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=0;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return w?x:-x;
}
int main()
{
n=read(),m=read();
for (reg int i=1;i<=n;i++) b[i]=b[i-1]^read();
for (reg int j=60;~j;j--)
{
int cnt=0;
for (reg int i=1;i<=n;i++)
if (!vis[i]&&(!(b[i]&(1ll<<j)))) ++cnt;
if (cnt>=m&&(!(b[n]&(1ll<<j))))
{for (reg int i=1;i<=n;i++) if (b[i]&(1ll<<j)) vis[i]=1;}
else ans|=(1ll<<j);
}
printf("%lld\n",ans);
return 0;
}
```