洛谷5283 [十二省联考2019]异或粽子

~~话说我题目难度的数据该更新了，这个bug信息先鳖管它~~ UPD2019.4.12:更新完毕

不得不说洛谷评测机真的慢，loj和jxoj都跑过了，在洛谷我硬是试了半天才过。~~JXOJ比你们洛谷不知道高到哪里去了~~

我做法跟大部分题解一样，其实是看了题解我才会做的。还是应用连续异或的性质，直接存异或的前缀和 $s[i]$ ，求区间 $\left[ l,r \right]$ 的异或即为：

$$\bigoplus_{i=l}^r a_i=s_r\oplus s_{l-1}$$

例题：https://www.codechef.com/problems/REBXOR

然后这道题就变成了求前 $k$ 大的两两异或值的和。

要求前 $k$ 大的和，有点像序列合并，可以用堆来维护。

参考：https://www.luogu.org/blog/gkxx-is-here/solution-p5283

考虑一个优化：我们在枚举区间 $\left[ l,r \right]$ 这一步，可以只枚举一个右端点 $r$ ，然后在 $\left[0,r-1\right]$ 上找到一个与 $s_r$ 异或值最大的 $s_l$ ，那么 $s_l \oplus s_r$ 即为 $\left[1,r\right]$ 上的最大异或和。

首先将所有前缀和加入堆，然后我们从堆中连续取 $k$ 次，当取出一个元素时，首先把它加入答案，然后假设它是所在前缀的第 $rk$ 大异或和，我们只要查询那个前缀的第 $rk+1$ 大异或和，加入堆里即可。

显然堆中元素是一个三元组 $(sum,now,rk)$ ，分别是前缀和、当前的 $r$ 和当前是第几大的前缀和。排序显然是按照 $sum$ 从大到小。

求区间第 $rk$ 大异或和可以用可持久化字典树，套模板就行了。

我懒得重载运算符，然后就写了个巨难看的pair套pair。

还有注意要开long long，我看了题解没踩这个坑，然后因为没用1ll调了半天。

洛谷上卡常严重，最开始我开O2都过不了，O3也不管用。最后是把所有对优先队列的push()全部换成emplace()~~趁着评测低峰~~交c++11才勉强卡过的。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define mp make_pair
#define N 500005

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

priority_queue <pair<ll,pr> > q;
ll rt[N],val[N<<6],vis[N<<6][2],s[N],cnt,n,m;

inline void build(ll x,ll now,ll last)
{
    for (ll i=32;i>=0;i--)
    {
        val[now]=val[last]+1;
        ll nxt=(x>>i)&1;
        if (!vis[now][nxt]) vis[now][nxt]=++cnt;
        vis[now][nxt^1]=vis[last][nxt^1];
        now=vis[now][nxt];
        last=vis[last][nxt];
    }
    val[now]=val[last]+1;
}

inline ll query(ll x,ll now,ll kth)
{
    ll ans=0;
    for (ll i=32;i>=0;i--)
    {
        ll nxt=(x>>i)&1;
        if (val[vis[now][nxt^1]]<kth)
        {
            kth-=val[vis[now][nxt^1]];
            now=vis[now][nxt];
        }
        else
        {
            ans+=(1ll<<i);
            now=vis[now][nxt^1];
        }
    }
    return ans;
}

int main()
{
    n=read(); m=read();
    for (ll i=1;i<=n;i++) 
    {
        s[i]=s[i-1]^read();
        rt[i]=++cnt;
        build(s[i-1],rt[i],rt[i-1]);
    }
    for (ll i=1;i<=n;i++) q.emplace(mp(query(s[i],rt[i],1),mp(i,1)));
    ll ans=0;
    for (ll i=1;i<=m;i++)
    {
        ll sum=q.top().first,now=q.top().second.first,rk=q.top().second.second; q.pop();
        ans+=sum;
        if (rk<=now) q.emplace(mp(query(s[now],rt[now],rk+1),mp(now,rk+1)));
    }
    printf("%lld",ans);
    return 0;
}

新评论