洛谷P5283 & LOJ3048：[十二省联考2019]异或粽子——题解

青旅半醒 2022-01-05 04:55 206阅读 0赞

[https://www.luogu.org/problemnew/show/P5283][https_www.luogu.org_problemnew_show_P5283]

[https://loj.ac/problem/3048][https_loj.ac_problem_3048]

> 小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
> 
> 小粽面前有 n 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 1 到 n。第 ii 种馅儿具有一个非负整数的属性值 a\_i。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 k 个粽子。
> 
> 小粽的做法是：选两个整数数 l, r，满足 1⩽l⩽r⩽n，将编号在 \[l,r\] 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 `ˆ` 运算符或 Pascal 中的 `xor` 运算符）
> 
> 小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的 粽子。
> 
> 小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

**UPD：手痒了于是还是把代码写了……**

不要在意我只是突然诈了一个尸。

以及场外选手题解口胡之后看了一下正解发现差不多？

正好一直想要诈一个尸，就用这个诈一个尸吧。

顺（主）便（要）聊聊心路历程。

——————

看到异或取最大第一眼想到线性基，然后看到连续的数就想到了[BZOJ3261：最大异或和][BZOJ3261] 。（天哪我记性真好一年前的东西我还记得）

然而此时并看不出二者的关系。

然后想暴力，枚举$O(n^2)$，但$k$与$n$并非一个数量级的。

于是想到了[BZOJ2006：\[NOI2010\]超级钢琴][BZOJ2006_NOI2010] 对前$k$大值的处理方法。（天哪我记性真好一年前的东西我还记得\*2）

而超级钢琴那道题我们是用了st表维护的，但是异或显然不能用st表维护。

那就可持久化trie呗！顺理成章的联系到了一起。

于是题解如下：首先预处理前缀异或和$s$，建立可持久化trie，则原$\[l,r\]$的异或和即为$s\[r\] \\; xor \\; s\[l-1\]$。

于是固定$l$求$r$使得$s\[r\] \\; xor \\; s\[l-1\]$尽可能的最大（设为$w$吧），然后将这些信息一起扔到堆里面（同时我们把$r$所在的范围$L,R$一起扔里面）。

每次弹出一个$(l,r,w,L,R)$的时候，我们就要找第二大的$\[l,r\]$扔进去，超级钢琴告诉我们，第二大的$r$一定在$\[L,r-1\]$和$\[r+1,R\]$当中，我们干脆把区间分成两份各求一遍直接都扔进去就好了。

复杂度一个建trie$O(nloga\_i)$一个预处理$O(nloga\_i)$一个弹$O(kloga\_i)$。

（老年选手不会算复杂度了不知道对不对orz）

另外洛谷需要开O2

#include<cstdio>
    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #include<cctype>
    using namespace std;
    typedef long long ll;
    const int N=5e5+5;
    const int B=33;
    inline ll read(){
        ll X=0,w=0;char ch=0;
        while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
        while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        return w?-X:X;
    }
    struct node{
        int son[2],sum,num;
    }tr[50*N];
    int tot,rt[N],pool;
    ll s[N];
    void insert(int y,int &x,ll k,int pos,int now){
        tr[x=++pool]=tr[y];tr[x].sum++;
        if(now<0){tr[x].num=pos;return;}
        bool p=k&(1LL<<now);
        insert(tr[y].son[p],tr[x].son[p],k,pos,now-1);
        return;
    }
    int query(int nl,int nr,ll k,int now){
        if(now<0)return tr[nr].num;
        bool p=k&(1LL<<now);
        int delta=tr[tr[nr].son[p^1]].sum-tr[tr[nl].son[p^1]].sum;
        if(delta>0)return query(tr[nl].son[p^1],tr[nr].son[p^1],k,now-1);
        else return query(tr[nl].son[p],tr[nr].son[p],k,now-1);
    }
    struct data{
        int l,r;
        ll w;
        int L,R;
        bool operator <(data b)const{
            return w<b.w;
        }
    };
    priority_queue<data>q;
    int main(){
        int n=read(),k=read();
        for(int i=1;i<=n;i++)s[i]=s[i-1]^read();
        for(int i=1;i<=n;i++)insert(rt[i-1],rt[i],s[i],i,B);
        for(int i=1;i<=n;i++){
            int l=i;int r=query(rt[l-1],rt[n],s[l-1],B);
            q.push((data){l,r,s[r]^s[l-1],l,n});
        }
        ll ans=0;
        while(k--){
            data tmp=q.top();q.pop();
            ans+=tmp.w;
            int i=tmp.l,j=tmp.r;
            if(tmp.L<=j-1){
                int t=query(rt[tmp.L-1],rt[j-1],s[i-1],B);
                q.push((data){i,t,s[t]^s[i-1],tmp.L,j-1});
            }
            if(j+1<=tmp.R){
                int t=query(rt[j],rt[tmp.R],s[i-1],B);
                q.push((data){i,t,s[t]^s[i-1],j+1,tmp.R});
            }
        }
        printf("%lld\n",ans);
        return 0;
    }

\+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：[http://www.cnblogs.com/luyouqi233/][http_www.cnblogs.com_luyouqi233]\+

\+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/10662354.html

[https_www.luogu.org_problemnew_show_P5283]: https://www.luogu.org/problemnew/show/P5283
[https_loj.ac_problem_3048]: https://loj.ac/problem/3048
[BZOJ3261]: https://www.cnblogs.com/luyouqi233/p/8527581.html
[BZOJ2006_NOI2010]: https://www.cnblogs.com/luyouqi233/p/8964616.html
[http_www.cnblogs.com_luyouqi233]: http://www.cnblogs.com/luyouqi233/