题目描述
给出一个长度为 $m$ 的序列 $a$ ，编号为 $a_1\sim a_m$，其中 $n$ 个位置的数已经确定，剩下的位置的数可以任意指定。现在令 $b$ 表示 $a$ 的前缀异或和，求 $\sum\limits_{i=1}^mb_i$ 的最小值。
输入
输入第一行两个非负整数n,m,分别表示原始序列a的长度及剩余元素的个数。之后m行，每行2个数i,ai，表示一个剩余元素的位置和数值。1<=N<=10^9,0<=M<=Min(n,10^5),0<=ai<=10^9注意未知的 ai 可以超过已知 ai 的范围。保证输入中所有的 i 不同，且满足 1 ≤ i ≤ n。
输出
输出一个整数表示可能的最小值
样例输入
5 3
4 0
3 7
5 0
样例输出
7
题解
拆位+乱搞
首先容易发现：每一个连续段的影响是独立的。
进一步可以发现：对于两个连续段之间没有填数的一段，该未填段除最后一个数以外的数的异或和均在取0（显然可以取到）时最优，而该未填段最后一个数只对自己以及后面的连续段产生影响。
更加具体地，若该未填段的最后 $b_i$ 是 $x$ ，后面连续段的数的前缀异或和为 $c_1\sim c_l$ ，则代价就是 $x+\sum\limits_{i=1}^lx\ xor\ c_i$ 。
显然每一位互不影响，于是我们可以拆位，统计出前缀异或和中该位0和1的个数，进而判断 $x$ 的这一位取0和取1时哪一个更优，然后计算答案即可。
这里需要注意一个坑点：如果第一个连续段是从第一个位置开始的，由于没有前一个位置，不能“钦定”最优解，需要特判这种情况，直接计算。
时间复杂度 $O(n\log n)$
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
struct data
{
int p , v;
bool operator<(const data &a)const {return p < a.p;}
}a[N];
int s[N] , cnt[31] , tot;
int main()
{
int m , i , j , c;
long long ans = 0;
scanf("%*d%d" , &m);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &a[i].p , &a[i].v);
sort(a + 1 , a + m + 1);
for(c = 1 ; c <= m ; c ++ )
{
tot = 1 , s[1] = a[c].v;
while(c < m && a[c + 1].p - a[c].p == 1)
tot ++ , s[tot] = a[++c].v ^ s[tot - 1];
if(!(c - tot) && a[1].p == 1)
for(i = 1 ; i <= tot ; i ++ )
ans += s[i];
else
{
for(i = 0 ; i < 30 ; i ++ )
{
cnt[i] = 0;
for(j = 1 ; j <= tot ; j ++ )
if(s[j] & (1 << i))
cnt[i] ++ ;
ans += (1ll << i) * min(cnt[i] , tot - cnt[i] + 1);
}
}
}
printf("%lld\n" , ans);
return 0;
}
