题解 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。

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

std::set<int>！ovo

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

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

待插入的整数	对应的二进制表达（不足位补0）
(7)	((111)_2)
(5)	((101)_2)
(6)	((110)_2)
(2)	((010)_2)
(3)	((011)_2)

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

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

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

插入时，从高到低遍历数字二进制的每一位，并维护一个指针(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 ext { xor } 1)号儿子，那么走(x.son[k ext { xor } 1])会更优。

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

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

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

回到正题

题目要求(m)个([l, r])点对。点对是有序的，为了方便，先将(m imes 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 imes 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
", ans / 2);
  return 0;
}

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

(huge extbf {程序千万行，})

(huge extbf {long long 第一行；})

(huge extbf {类型不规范，})

(huge extbf {WA两行泪。})

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

滑稽