Description
qmqmqm希望给sublinekelzrip出一道可做题。于是他想到了这么一道题目：给一个长度为n的非负整数序列ai,你需
要计算其异或前缀和bi,满足条件b1=a1,bi=bi?1 xor ai(i≥2).但是由于数据生成器出现了问题，他生成的序列a
的长度特别长，并且由于内存空间不足，一部分ai已经丢失了，只剩余m个位置的元素已知。现在qmqmqm找到你，
希望你根据剩余的ai,计算出所有可能的a序列对应的b序列中∑=bi(1<=i<=N)的最小值。
Input
输入第一行两个非负整数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。
Output
输出一个整数表示可能的最小值
每位分别考虑，f[i][j]表示前i个数，异或和这一位为j，此时这一位至少有几个1
如果某个位置已被确定，直接计算，否则可以选择填0或1
f[i][0]=min(f[i-1][0],f[i-1][1])
f[i][1]=min(f[i-1][0],f[i-1][1])+1
可以发现这样推两步或以上值就不会变了，因此相邻多个未确定的数可以当做一个处理
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e6+;
int n,m;
struct pos{
int x,y;
bool operator<(const pos&w)const{return x<w.x;}
}ps[N];
i64 f[][];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)scanf("%d%d",&ps[i].x,&ps[i].y);
std::sort(ps+,ps+m+);
int px=;
for(int t=;t<=;++t)f[t][]=1ll<<;
for(int i=;i<=m;++i){
int x=ps[i].x,y=ps[i].y;
int d=x-px-;
if(d)for(int t=;t<=;++t){
i64 f0=f[t][],f1=f[t][];
f[t][]=std::min(f0,f1);
f[t][]=std::min(f0,f1)+;
}
for(int t=;t<=;++t){
int b=y>>t&;
i64 f0=f[t][],f1=f[t][];
if(b){
f[t][]=f1;
f[t][]=f0+;
}else{
f[t][]=f0;
f[t][]=f1+;
}
}
px=x;
}
i64 s=;
for(int t=;t<=;++t)s+=std::min(f[t][],f[t][])<<t;
printf("%lld\n",s);
return ;
}