#C241015B. 异或序列(xor)
标签（Label）
- 树状数组
- 二进制
前言（Front talk）
$\qquad$本来已经推到了枚举二进制，后面在考虑每一位的贡献的时候发现要考虑退位，不知怎么的就觉得不好处理，甚至得出了“减法无法用二进制处理”的“伟大”结论。。。
$\qquad$有想法就先抓住，不要轻易地放弃，最后就会找到方法。
$\qquad$和正解只差有关退位的分类讨论。。。
网址（Website）
题解（Solution）
$\qquad$发现对 $a[i]$ 排序，不会影响到答案，直接排序。由于二进制，考虑枚举答案的每一个二进制位，对应有 $2$ 种情况，即当前位为 $1$ 或 $0$ ，将其分为两组，容易发现对于两个当前二进制位相同的数 $a[i]$ 和 $a[j]$ ，他们相减后第 $k$ 位为 $1$ 当且仅当在一组中且相减不会向当前借位或者在不同组中，相减借位。很明显，对于一个数 $a[i]$ ，只需要找到所有同组中比它大的数和不同组中比它小的数即可。由于排序的影响，注意需要按顺序加入数字，否则会算重或算漏。
出题者题解
算法分析
对每一位单独考虑贡献，由于会有退位的影响，不能直接计算。先对该数组从小到大排序，对于第 $k$ 位上的贡献，考虑 $a_i$ 的二进制后缀（后 $k$ 位），大小记为 $x$（这里只考虑 $a_i$ 为大的数），可以被加入贡献的是二进制后缀大小在范围 $[0, x - 2^k]$ 或者 $(x, x + 2^k]$ 的数。
只需将 $a_1, a_2 \ldots a_{i-1}$ 的二进制后缀放入树状数组中进行查询即可。复杂度是 $\Theta(n \log n \log(10^{12}))$。（我们卡掉了指令集做法）（但是暴力跑 $n^2$ 可以拿 $\mathrm{70pts}$ ）
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int B = 40;
const int N = 201234;
bool ST;
int n,mx,ans;
int a[N],b[N],c[N];
struct BIT{
bool tt[N];int n;
inline void init(int siz){n = siz;memset(tt,0,sizeof tt);}
void update(int x){for(int i=x;i<=n;i+=(i&-i)) tt[i]^=1;}
bool ask(int x){bool res = 0;for(int i=x;i;i-=(i&-i))res^=tt[i];return res;}
}t[2];//使用异或树状数组
bool check(int k){
For(i,1,n) b[i] = c[i] = a[i]&((1ll<<k)-1);//快速获得二进制前k位
sort(c+1,c+n+1);int tot=unique(c+1,c+n+1)-c-1;
t[0].init(tot), t[1].init(tot);//通过建排名树状数组，避免离散化
bool res = false;
For(i,1,n){
int p = (a[i]>>k)&1, q = !p;//分两种树状数组维护
b[i] = lower_bound(c+1,c+tot+1,b[i]) - c;//找到b[i]的位置
res = res ^ t[p].ask(b[i]) ^ t[p].ask(tot);//在异或运算下，原来的乘法也可以使用异或
res = res ^ t[q].ask(b[i]);
t[p].update(b[i]);
}return res;
}
void solve(){
n = rd();For(i,1,n) a[i] = rd();
sort(a+1,a+n+1);
For(k,0,B) if(check(k)) ans+=(1ll<<k);
printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
int T = 1, Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
