202208

[TOC]

1. [十二省联考 2019] 异或粽子 [Euclid]

题面

给定一个长为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$，要求选出 $k$ 个不同（但可以相交）的区间 $[l,r]$ 使得每个区间的异或和之和最大

$1\le n\le5\times10^5,1\le k\le 2\times10^5,0\le a_i<2^{32}$

题解

我们只需要求出前 $k$ 大的区间异或和即可

显然可以通过前缀异或和把区间异或和转化为两个数的异或和

一种想法是用优先队列维护，将以每个数为右端点的最大的放入优先队列，取出一个数之后再放入次大的

不难发现查找次大的可以直接在 Trie 上走路实现

做法 1：暴力上可持久化 Trie，在前 $i-1$ 个数的基础上加入第 $i$ 个数，这样可以随时查询以任何一个数为右端点的答案

做法 2：取消 $l<r$ 的限制，这样就变成我们要选最大的 $2k$ 个区间，但只需要找出以每个数为端点的最大的区间即可，可以直接在全局的 Trie 上找

复杂度均为 $O(n\log a_i+k\log n\log a_i)$

2. [十二省联考 2019] 春节十二响 [Safe]

题面

给定一棵 $n$ 个点的数，点有点权，要求将这些点分为若干组，使得每组的最大值之和最小

$1\le n\le2\times10^5,1\le m\le10^9$

题解

从上到下贪心，用堆启发式合并两棵子树即可

复杂度 $O(n\log^2n)$