sol

对于每一个二进制位，如果要满足在逻辑与运算中造成贡献，那么必须全部是。

即对于一条树链，他的异或前缀和序列 全部是，我们把它异或差分转成正常的序列，即是需要满足，其他全部等于。整合一下，结论就是一个二进制位有贡献当且仅当根结点这一位是，其他全是。

找到所有中只有一次为的位，随便贪心一下即可。

#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fir first
#define sec second
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ll long long
#define int long long
const int maxn=5e5+10;
int a[maxn];
int cnt[maxn];
signed main()
{
    Ios();
	int n;
    cin>>n;
    REP(i,1,n) cin>>a[i];
    REP(i,1,n)
    REP(w,0,31)
    if((a[i]>>w)&1) cnt[w]++;
    int pos=-1;
    for(int i=31;i>=0;i--)
    if(cnt[i]==1){pos=i;break;}
    if(pos==-1)
    {
        cout<<0<<"\n";
        return 0;
    }
    REP(i,1,n)
    if((a[i]>>pos)&1)
    {
        int ans=0;
        REP(w,0,31)
        if(((a[i]>>w)&1)&&cnt[w]==1) ans+=(1ll<<w);
        cout<<ans<<"\n";
        return 0;
    }
}

暂无评论