题解 P5283 【[十二省联考2019]异或粽子】
hsfzLZH1
·
·
题解
题目大意
给定一个长度为 n 的数组 a_i ，你每次可以选择一个区间 [l,r] ，其价值为 val[l,r]=\bigoplus_{i=l}^r a_i 。求价值最大的 k 个不同区间的价值和。
1\le n\le 5\times 10^5,1\le k\le min\{\frac {n(n-1)} 2 ,2\times 10^5 \},0\le a_i\le 2^{32}-1
解题思路
此题是求解异或问题的常用 trick 综合。
观察到价值是 \bigoplus_{i=l}^r a_i ，我们可以定义 s_i=\bigoplus_{j=1}^i a_j ，那么 val[l,r]=s_{l-1}\oplus s_r 。特别的，有 s_0=0 。这样，我们不同的 i,j 满足 0\le i< j\le n ，对应的就是不同的区间。
题目转化为给定一个长度为 n+1 的数组 s_i ，求 i<j 时， s_i\oplus s_j 的 \frac {n(n+1)} 2 种取值中前 k 大的值的和。
我们将 $s_i$ 的 $n+1$ 个值插入 01 Trie ，给定一个 $k$ ，我们可以在 $O(log_2 a)$ 的时间复杂度内找到与 $a$ 异或结果第 $k$ 大的值。方法类似于在线段树上二分。
我们维护一个大根堆，堆中初始时加入每个 $s_i$ 与 $s$ 中元素异或的最大值。每次我们取出堆顶，累加进答案，如果我们取出的是 $s_i$ 与 $s$ 中元素异或的第 $t$ 大值，就在堆中插入 $s_i$ 与 $s$ 中元素异或的第 $t+1$ 大值。这样进行 $k$ 次操作，取出的依次就是 $s$ 中元素两两异或的前 $k$ 大值。
令 $a=\max \{a_i\}$，则时间复杂度为 $O((n+k)\log_2 a\log_2 n)$ 。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=500010;
typedef long long ll;
int n,k,cnt=1;
ll a[maxn],ans;
struct Trie
{
int ch[2],cnt;
}st[maxn*34];
void insert(ll v)
{
int nww=1;st[nww].cnt++;
for(ll i=33;i>=0;i--)
{
ll t=(v>>i)&1ll;
if(!st[nww].ch[t])st[nww].ch[t]=++cnt;
nww=st[nww].ch[t];st[nww].cnt++;
}
}
ll query(ll v,int k)
{
int nww=1;
ll ans=0;
for(ll i=33;i>=0;i--)
{
ll t=(v>>i)&1ll;
if(st[st[nww].ch[t]].cnt>=k)nww=st[nww].ch[t];
else k-=st[st[nww].ch[t]].cnt,nww=st[nww].ch[t^1],ans|=(1ll<<i);
}
return ans;
}
struct node
{
int id,rnk;ll v;
bool operator<(node x)const{return v<x.v;}
};
priority_queue<node>q;
int main()
{
scanf("%d%d",&n,&k);k*=2;
insert(0);for(int i=1;i<=n;i++)scanf("%lld",a+i),a[i]^=a[i-1],insert(a[i]);
for(int i=0;i<=n;i++)q.push({i,n+1,query(a[i],n+1)});
while(k--)
{
node x=q.top();q.pop();
ans+=x.v;
if(x.rnk)q.push({x.id,x.rnk-1,query(a[x.id],x.rnk-1)});
}
printf("%lld\n",ans/2ll);
return 0;
}
```
## 解法扩展
考虑简化后的问题，给定一个数组 $a_i$ ，求其中两两异的前 $k$ 大值的和。
以上给出的做法是与 $k$ 有关的，此题中 $k$ 的数据范围是和 $n$ 同阶，但是 $k$ 的范围最大可以达到 $O(n^2)$ ，此时有时间复杂度为 $O(n\log_2^2 a)$ 的做法。（与 $k$ 无关）
建立 Trie ，将每个 $a_i$ 插入 Trie， Trie 上一个结点子树的大小定义为其子树中有多少个 $a_i$ 。
首先我们考虑如何求两两异或的 **第 $k$ 大值** 。考虑从高到低按位确定第 $k$ 大值每一个二进制位的值。假设我们已经确定了所求第 $k$ 的值的前若干位，正在确定当前位的值。对于每个 $a_i$ ，在 Trie 上都有一个对应的子树使得子树中的叶子结点对应的值（即从根节点到该叶子结点的路径对应的值）与 $a_i$ 异或的前缀等于已经确定的第 $k$ 大值的前若干位。我们设这个子树是 $v$ 的子树。设与 $v$ 同层（深度相同）且在根节点到 $a_i$ 对应叶子结点的路径上的点为 $u$ 。
我们每次将 $u,v$ 下移一层（始终保持 $u$ 在根节点到叶子结点 $a_i$ 的路径上 ），同时确定第 $k$ 大值对应位的值。假设我们即将把 $u$ 往一个方向的儿子下移，我们统计对每一个 $a_i$ 把 $v$ 向另一个方向移动的子树的大小之和 $tot$ 。$tot$ 即为第 $k$ 大值的这一位是 $1$ 时，满足 $a_i\oplus a_j$ 的相同位也是 $1$ 且与第 $k$ 大值之前已经确定的位数也相同的数对 $(i,j)$ 的组数。如果 $tot\ge k$ ，说明有多于 $k$ 个这样的对，第 $k$ 大值的这一位是 $1$ ，反之这一位是 $0$ ，此时还要将 $k$ 的值减去 $tot$ ，即求符合前缀相同条件的第 $k-tot$ 大值。根据求出的 $k$ 对应位的值，更新所有的 $u,v$ ，便于求解更低位。
求第 $k$ 大值的时间复杂度为 $O(n\log_2 a)$ 。
求出第 $k$ 大值后，我们考虑如何求前 $k$ 大值的和。在以上的过程中，我们剩下的 $k$ 的值即为前 $k$ 大值中与第 $k$ 大值相等的数的个数，那么，我们只需求出两两异或值大于第 $k$ 大值的异或值的和即可。
枚举每一个 $a_i$ ，同样从高位到低位求解。若两两异或的第 $k$ 大值的这一位是 $0$ ，则 $a_i$ 与 $\{$与 $u$ 这一层下移方向相反的子树 $\}$ 中叶子结点的对应值的异或值大于第 $k$ 大值。这样的子树最多有 $O(\log_2 a)$ 个。现在我们要解决的问题是如何求 $a_i$ 与某一子树中的值的异或值之和。
并不用 $O(n\log_2^2 a)$ 的空间处理存储， Trie 上一子树中的值在排序后的数组中是连续的一段。我们将 $a_i$ 数组排序，并不会影响之前的处理，然后处理出其每一位上 $1$ 的个数的前缀和，需要求值时找到子树中的最小值和最大值，对应数组中的左右端点，差分求值即可。由于我们要按位计算，单次求值的时间复杂度为 $O(\log_2 a)$ 。
总的时间复杂度为 $O(n\log_2^2 a)$ ，空间复杂度为 $O(n\log_2 a)$ 。
注意 `long long` ，特别是移位时， `(1<<i)` 是 `int` 型的，要写成 `(1ll<<i)` ！
## 代码展示
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int maxn=500010;
int n,k,a[maxn],kth,ans,tot;
int cnt,ch[maxn*40][2],minn[maxn*40],maxx[maxn*40],siz[maxn*40],nww,t,p[maxn];
int cnt1[maxn][40];
int calc(int v,int l,int r)
{
if(l==0)return 0;
int ret=0;
for(int i=33;i>=0;i--)
{
int chx=(v>>i)&1;
if(chx==0)ret+=(1ll<<i)*(cnt1[r][i]-cnt1[l-1][i]);
else ret+=(1ll<<i)*(r-l+1-cnt1[r][i]+cnt1[l-1][i]);
}
return ret;
}
main()
{
scanf("%lld%lld",&n,&k);k*=2;
for(int i=1;i<=n;i++)scanf("%lld",a+i);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)for(int j=0;j<=33;j++)if((a[i]>>j)&1)cnt1[i][j]=cnt1[i-1][j]+1;else cnt1[i][j]=cnt1[i-1][j];
cnt=1;
for(int i=1;i<=n;i++)
{
nww=1;siz[nww]++;
for(int j=33;j>=0;j--)
{
int chx=(a[i]>>j)&1;
if(!ch[nww][chx])ch[nww][chx]=++cnt,minn[cnt]=i;
nww=ch[nww][chx];maxx[nww]=i;siz[nww]++;
}
}
for(int i=1;i<=n;i++)p[i]=1;
for(int i=33;i>=0;i--)
{
tot=0;
for(int j=1;j<=n;j++)
{
int chx=((a[j]>>i)&1)^1;
tot+=siz[ch[p[j]][chx]];
}
if(k<=tot)t=1,kth|=(1ll<<i);
else k-=tot,t=0;
for(int j=1;j<=n;j++)
{
int chx=((a[j]>>i)&1)^t;
p[j]=ch[p[j]][chx];
}
}
//printf("%lld\n",kth);
for(int i=1;i<=n;i++)
{
nww=1;
for(int j=33;j>=0;j--)
{
int chx=((a[i]^kth)>>j)&1;
if(((kth>>j)&1)==0&&ch[nww][chx^1])ans+=calc(a[i],minn[ch[nww][chx^1]],maxx[ch[nww][chx^1]]);
nww=ch[nww][chx];
}
}
printf("%lld\n",(ans+k*kth)/2ll);
return 0;
}
```
总结一下本题中相关的 trick ：
1. 做异或前缀和，区间异或和转化为两数异或和；
2. 补全上三角形转化为求矩形的值；
3. 求两两异或的第 $k$ 大值：从高位到低位， Trie 上贪心；
4. 求一个值与静态 Trie 上一个子树中的值的异或和的和： Trie 上子树中的值在排序后数组上是连续的。