[十二省联考2019]异或粽子 题解
Problem
给定(n)个数(A_i),选择不同的(m)个区间([L,R])使得(sumlimits_{i=1}^m igotimeslimits_{j=L_i}^{R_i}A_j)最大
Solution
先做前缀和,使得(A_i=igotimeslimits_{j=1}^i A_j),这样题目转化成选出异或值最大的(m)对
至于怎么去算这个东西,可以尝试去二分一个答案下界,即这(m)个数都大于(mid),我们考虑怎么去判合不合法
枚举肯定不行,考虑一次算出以(l)为左端点时有多少个(A_l otimes A_r geq mid(r > l)),我们考虑把([l+1,n])全部插入一个01Trie中,在Trie树上统计
记当前位(A_l)的值为(k),(mid)的值为(p)。倘若(p=0),则个数为(k otimes 1)的节点个数加上递归进入(k otimes 0)的答案;倘若(p=1),则个数为进入(k otimes 1)的答案
统计答案时进入Trie中dfs即可
这样每次二分都要重建Trie树,持久化之后就不用每次都建了
这个算法说不定能过面对(5 imes 10^5)的数据还是略显乏力,考虑还能怎么优化
上面的算法的瓶颈在于二分,考虑直接在Trie上二分,这样可以少掉一个(log)
把所有数丢到Trie上一起二分,倘若当前结点右儿子的大小大于当前剩余对数,则全部往右儿子走,下界把当前位赋一;否则就往左儿子走
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m;
LL ans,lim,sum;
LL A[500005],cur[500005],root[500005];
struct Trie{
int tot;
int son[20000005][2],size[20000005];
void insert(int u,int p,int d,LL val){
size[u]=size[p]+1;
if(d==-1)
return;
int k=(val>>d)&1;
son[u][k]=++tot;
son[u][k^1]=son[p][k^1];
insert(son[u][k],son[p][k],d-1,val);
return;
}
LL solve(int d,int now,LL val){
if(d==-1)
return val;
LL sum=0;
for(register int i=1;i<=n;++i){
int k=(A[i-1]>>d)&1;
sum+=size[son[cur[i]][k^1]];
}
if(now>sum){
now-=sum;
for(register int i=1;i<=n;++i){
int k=(A[i-1]>>d)&1;
cur[i]=son[cur[i]][k];
}
return solve(d-1,now,val);
}
else{
for(register int i=1;i<=n;++i){
int k=(A[i-1]>>d)&1;
cur[i]=son[cur[i]][k^1];
}
return solve(d-1,now,val+(1LL<<d));
}
}
LL count(int u,int d,LL val,LL lim){
if(!u)
return 0;
if(d==-1)
return size[u];
int k=(val>>d)&1;
int p=(lim>>d)&1;
if(p)
return count(son[u][k^1],d-1,val,lim);
else
return size[son[u][k^1]]+count(son[u][k],d-1,val,lim);
}
LL Calcu(int u,int d,int op,LL val,LL lim,LL sum){
if(!u)
return 0;
if(d==-1)
return sum*size[u];
int k=(val>>d)&1;
int p=(lim>>d)&1;
if(op)
return Calcu(son[u][k^1],d-1,1,val,lim,sum+(1LL<<d))+Calcu(son[u][k],d-1,1,val,lim,sum);
else if(!p)
return Calcu(son[u][k^1],d-1,1,val,lim,sum+(1LL<<d))+Calcu(son[u][k],d-1,0,val,lim,sum);
else
return Calcu(son[u][k^1],d-1,0,val,lim,sum+(1LL<<d));
}
}T;
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
int main(){
n=read();m=read();
for(register int i=1;i<=n;++i)
A[i]=A[i-1]^read();
T.tot=n;
for(register int i=1;i<=n;++i)
root[i]=i;
for(register int i=n;i>=1;--i)
T.insert(root[i],root[i+1],32,A[i]);
for(register int i=1;i<=n;++i)
cur[i]=root[i];
lim=T.solve(32,m,0);
for(register int i=1;i<=n;++i)
sum+=T.count(root[i],32,A[i-1],lim);
for(register int i=1;i<=n;++i)
ans+=T.Calcu(root[i],32,0,A[i-1],lim,0);
if(sum>m)
ans-=lim*(sum-m);//可能选多了,把多的减去
printf("%lld
",ans);
return 0;
}