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

时间：2019.4.20

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 \(n\) 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 \(1\) 到 \(n\) 。第 \(i\) 种馅儿具有一个非负整数的属性值 \(a_i\) 。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 \(k\) 个粽子。

小粽的做法是：选两个整数数 \(l\), \(r\) ，满足 \(1 \leqslant l \leqslant r \leqslant n\)，将编号在 \([l, r]\) 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ? 运算符或 Pascal 中的 xor 运算符）

小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的 粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

分析

注意：下文为了方便，均用 \(m\) 代替了原题中的 \(k\)

作为十二省联考的原题，这题也应该算是简单题了吧QwQ......

题目要求前\(m\)大的异或部分和总和，先预处理出前缀异或和\(sum[i]\)，问题变成求前\(m\)大的异或值对总和。

异或？当然是用01-Trie啦！

01-Trie（大佬跳过QAQ）

字典树（Trie）是一种用于存储字符串的数据结构，限于篇幅便不在此赘述。我们只考虑Trie的一个变种：01-Trie。

如果我们要维护一种数据结构，支持在\(\bf {O(log\ n)}\)内插入整数、查询整数是否存在，要怎么做？

• std::set<int>！ovo

01-Trie为我们提供了一种新的思路：将整数按照二进制拆分，并一个一个bit存起来。

讲的不清楚？让我们看一看样例：

看起来很简单，是吧？对应的01-Trie长这样：

这棵Trie是每个数字按照二进制从高位到低位插入得到的。比如数字\(3\)对应着下图中红色标出的一条路径。

把上面的数字都在Trie里面查一查试试吧！每个数字在Trie中都有一条对应的路径，因此Trie最多有\((n \times \text {二进制位数})\)个节点（而且这是松的上界）。

插入时，从高到低遍历数字二进制的每一位，并维护一个指针\(x\)在树上移动。\(x\)一开始指向根节点（\(1\)号节点）。若当前位上的值是\(k\)，那么判断一下\(x\)是否有\(k\)号儿子，没有则新建，然后将\(x\)移动到\(x.son[k]\)，直到走完二进制的每一位为止。

查询类似，只不过没有新建节点而已。插入和查询的时间复杂度都是\(O(\log n)\)。

const int kLen = 32;
struct Node {
  int son[2];
};
Node tree[kMaxN];
int top;
void Insert(int val) {
  int x = 1;
  for (int i = kLen - 1; i >= 0; i--) { // 遍历二进制每一位
    bool k = bool(val & (1 << i)); // 获得当前位上的值
    if (!tree[x].son[k]) tree[x].son[k] = ++top; // 若儿子不存在则新建节点
    x = tree[x].son[k]; // 移动指针
  }
}

第\(k\)大异或和

01-Trie维护二进制这一特殊性质，使得01-Trie可以很方便地处理异或问题。

我们现在有了一棵01-Trie，想要查询某个数与其中数字的第\(rank\)大异或和，怎么办？

类似主席树，我们在Trie上的每个节点维护siz，表示插入时经过这个节点的次数。

首先，根据贪心策略，若当前位上的值是\(k\)，且\(x\)有\(k \text { xor } 1\)号儿子，那么走\(x.son[k \text { xor } 1]\)会更优。

这是因为走这一步可以使异或和的这一位变成\(1\)，而我们是从高位往低位走的，所以肯定会更优。

每走到一位，判断\(siz(x.son[k \text { xor } 1])\)是否大于等于\(rank\)，如果是，就说明第\(rank\)大异或和在\(x\)的第\(k \text { xor } 1\)号儿子中，并让\(x = x.son[k \text { xor } 1]\)。否则让\(x = x.son[k]\)，然后将\(rank\)减去\(siz(x.son[k \text { xor } 1])\)。

这样，我们就可以求出某个数在这棵Trie中的第\(rank\)大异或和了。

回到正题

题目要求\(m\)个\([l, r]\)点对。点对是有序的，为了方便，先将\(m \times 2\)，输出答案时再把答案减半。

首先，将输入数组\(a\)求一遍前缀异或和，然后将\(sum\)全部插入Trie中。

对于每个\(r\)，贪心告诉我们要按顺序取出它在Trie中的第\(1\)大、第\(2\)大、第\(3\)大...异或和。我们不知道每个\(r\)要取出多少个异或和，但是我们需要取出所有\(r\)中的前\(m\)个。一开始将每个\(r\)取出的第\(1\)大异或和放到堆（大根）中，每次取出堆顶并弹出。假设堆顶是\(r_0\)的第\(rank_0\)大异或和，那么我们将\(r_0\)的第\(rank_0 + 1\)大异或和压进堆里。这样重复\(m\)次，我们就能取出前\(m\)大的异或和。

实现上，使用结构体

struct Node {
  int index; // `r`的下标
  int rank; // 当前的排名
  LL value; // 第rank大异或值
};
bool operator<(const Node& x, const Node& y) { // 运算符重载
  return x.value < y.value;
} 

来表示上文堆的节点。循环\(m\)（或者说\(m \times 2\)）次即可。时间复杂度：\(O(32n + (32 + \log n)m)\)。卡常预警

代码

评测记录（O2）最大一个点1642ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int kMaxN = 5 * 100000 + 10;
const int kLen = 33;
const int kMaxSize = kMaxN * (kLen + 2) + 10;
struct Trie {
  struct Node {
    int son[2], siz;
  };
  Node tree[kMaxSize];
  int top;
  Trie() { top = 1; }
  void Insert(LL val) {
    int x = 1;
    for (int i = kLen - 1; i >= 0; i--) {
      bool k = bool(val & (1ll << i));
      tree[x].siz++;
      if (!tree[x].son[k]) tree[x].son[k] = ++top;
      x = tree[x].son[k];
    }
    tree[x].siz++;
  }
  LL Query(LL val, int rank) { // Query the k-th xor value of `val`
    int x = 1;
    LL ans = 0;
    for (int i = kLen - 1; i >= 0; i--) {
      bool k = bool(val & (1ll << i));
      /*if (!tree[x].son[!k]) {
        x = tree[x].son[k];
      } else */
      if (rank <= tree[tree[x].son[!k]].siz) {
        ans |= (1ll << i);
        x = tree[x].son[!k];
      } else {
        rank -= tree[tree[x].son[!k]].siz;
        x = tree[x].son[k];
      }
    }
    return ans;
  }
};
struct Node {
  int index, rank;
  LL value;
};
bool operator<(const Node& x, const Node& y) {
  return x.value < y.value;
}
priority_queue<Node> Q;
Trie T;
int n, m;
LL sum[kMaxN], a[kMaxN];
int main() {
  scanf("%d %d", &n, &m);
  m *= 2;
  sum[0] = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    sum[i] = a[i] ^ sum[i - 1];
  }
  for (int i = 0; i <= n; i++) {
    T.Insert(sum[i]);
  }
  for (int i = 0; i <= n; i++) {
    Q.push((Node) {i, 1, T.Query(sum[i], 1)});
  }
  LL ans = 0;
  for (int i = 1; i <= m; i++) {
    Node x = Q.top();
    Q.pop();
    ans += x.value;
    int idx = x.index;
    int rank = x.rank;
    if (rank <= n - 1) {
      Q.push((Node) {idx, rank + 1, T.Query(sum[idx], rank + 1)});
    }
  }
  printf("%lld\n", ans / 2);
  return 0;
}

\(\huge \textbf {北京市第三区交通委提醒您：}\)

\(\huge \textbf {程序千万行，}\)

\(\huge \textbf {long long 第一行；}\)

\(\huge \textbf {类型不规范，}\)

\(\huge \textbf {WA两行泪。}\)

• 一定要写(1ll << i)，而不是(1 << i)！！！

滑稽

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

原文：https://www.cnblogs.com/longlongzhu123/p/10742745.html