题解 P5283 【[十二省联考2019]异或粽子】
Owen_codeisking
2019-04-07 10:10:46
我居然在有生之年切掉了一道十二省联考的题?
做法跟超级钢琴超像,可以出门右拐。
### 可持久化 $01trie$ + 堆
我们求一遍前缀异或和,那么 $[l,r]$ 的异或和为 $sum_{l-1}\ \text{xor}\ sum_r$
我们先固定右端点 $r$,然后在 $[0,r-1]$ 查一个数异或 $sum_r$ 最大。这个可以用可持久化 $01trie$ 实现。
我们将 $n$ 个数放入堆中,每次取出最大的那个状态。设这个状态左端点在 $[l,r]$ ,与 $sum_x$ 异或起来最大的位置在 $k$,那么我们把状态的左端点分割成 $[l,k-1]$ 和 $[k+1,r]$ 后放入堆中。
时间复杂度 $O(n\log n)$
注意:下面这段代码不开加 $2K$ 的 $pragma$ 会被卡常,所以看看就好。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500000+10;
int n,k,rt[maxn],cnt;ll a[maxn],ans;
struct node
{
int ch[2],siz,id;
}t[maxn*40];
inline ll read()
{
register ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
void insert(int &now,int pre,int bit,int id,ll val)
{
now=++cnt;t[now]=t[pre];t[now].siz++;
if(bit==-1){t[now].id=id;return;}
if((val>>bit)&1) insert(t[now].ch[1],t[pre].ch[1],bit-1,id,val);
else insert(t[now].ch[0],t[pre].ch[0],bit-1,id,val);
}
int query(int u,int v,int bit,ll val)
{
if(bit==-1) return t[v].id;
int d=(val>>bit)&1;
if(t[t[v].ch[d^1]].siz-t[t[u].ch[d^1]].siz>0) return query(t[u].ch[d^1],t[v].ch[d^1],bit-1,val);
return query(t[u].ch[d],t[v].ch[d],bit-1,val);
}
struct State
{
int l,r,x,id;ll val;
State(int _l=0,int _r=0,int _x=0)
{
l=_l;r=_r;x=_x;
id=query(rt[l-1],rt[r],31,a[x]);
val=a[x]^a[id-1];
}
};
inline bool operator < (const State &a,const State &b)
{
return a.val<b.val;
}
priority_queue<State> pq;
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=a[i-1]^read();
for(int i=1;i<=n;i++) rt[i]=rt[i-1],insert(rt[i],rt[i],31,i,a[i-1]);
for(int i=1;i<=n;i++) pq.push(State(1,i,i));
while(k--)
{
State u=pq.top();pq.pop();ans+=u.val;
if(u.l<u.id) pq.push(State(u.l,u.id-1,u.x));
if(u.id<u.r) pq.push(State(u.id+1,u.r,u.x));
}
printf("%lld\n",ans);
return 0;
}
```