题解 P5283 【[十二省联考2019]异或粽子】

Owen_codeisking

2019-04-07 10:10:46

Solution

我居然在有生之年切掉了一道十二省联考的题? 做法跟超级钢琴超像,可以出门右拐。 ### 可持久化 $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; } ```