C++ 解法, 执行用时: 931ms, 内存消耗: 183216K, 提交时间: 2022-01-20 22:11:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[200005],c[200005][2],st[200005],top,ch[3000005][2],cnt[3000005][15];
int rt[200005],tot,sz[3000005],s[200005];
ll ans=0;
vector<int> val[200005];
void Find(int p,int nd,int x){
	//所有max(nd,x^y)的和
	if(!p)return ;
	for(int i=12;i>=0;i--){
		int w=(x>>i)&1;
		if(nd&(1<<i)){
			ans+=1ll*sz[ch[p][w]]*nd;
			p=ch[p][w^1];
		}
		else {
			int u=ch[p][w^1];
			for(int j=0;j<=12;j++){
				if((x>>j)&1){
					ans+=(sz[u]-cnt[u][j])*(1ll<<j);
				}
				else ans+=cnt[u][j]*(1ll<<j);
			}
			p=ch[p][w];
		}
		if(!p)return ;
	}
	ans+=1ll*sz[p]*nd;
}
void Ins(int &p,int x){
	if(!p)p=++tot;
	int q=p;
	for(int i=12;i>=0;i--){
		int w=(x>>i)&1;
		if(!ch[q][w])ch[q][w]=++tot;
		q=ch[q][w],sz[q]++;
		for(int j=0;j<=12;j++)if((x>>j)&1)cnt[q][j]++;
	}
}
int Merge(int p,int q){
	if(!p||!q)return p+q;
	sz[p]+=sz[q];
	for(int i=0;i<=12;i++)cnt[p][i]+=cnt[q][i];
	ch[p][0]=Merge(ch[p][0],ch[q][0]);
	ch[p][1]=Merge(ch[p][1],ch[q][1]);
	return p;
}
void dfs(int x,int L,int R){
	if(c[x][0])dfs(c[x][0],L,x-1);
	if(c[x][1])dfs(c[x][1],x+1,R);
	int p=c[x][0],q=c[x][1];
	Find(rt[p],a[x],s[x]);
	if(val[p].size()>val[q].size())swap(p,q);
	swap(val[q],val[x]);
	for(int i:val[p]){
		Find(rt[q],a[x],i);
		val[x].push_back(i);
	}
	ans+=max(a[x],s[L-1]^s[x]);
	Find(rt[c[x][1]],a[x],s[L-1]);
	val[x].push_back(s[x]);
	rt[x]=Merge(rt[p],rt[q]);
	Ins(rt[x],s[x]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]),s[i]=s[i-1]^a[i];
		while(top&&a[st[top]]>a[i])top--;
		int p=st[top];
		c[i][0]=c[p][1],c[p][1]=i,st[++top]=i;
	}
	dfs(st[1],1,n),cout<<ans;
}