比赛链接

Upsolved by nikkukun.

给定 $n \leq 2 \times 10^5$ 个 $[0, 2^{18})$ 内的数，求用恰好 $1, 2, \ldots, n$ 个数能异或出来的最大值。

根据线性基的特性，只要用基底的个数个线性无关的基就能获得最大值，因此 $i$ 并非很小的时候只要在 $i-2$ 答案的基础上随便加上两个相同的数即可。

令 $f(i)$ 表示 $a_i$ 是否出现，则做 $i$ 次异或 FWT 就能得到 $i$ 个数能否表示出来的答案，这里选择处理前 20 次即可。

Solved by nikkukun.

给定 $n \times m$ 的矩阵，第 $i$ 行 $j$ 列的数是 $\mathrm{lcm}(i, j)$，求所有 $k \times k$ 子矩阵最大值的和。

降维，做两次单调队列。

Solved by nikkukun.

给 $n$ 个数 $a_1, a_2, \ldots, a_n$ 和 $m \leq \min(n, 40000)$ 个数 $b_1, b_2, \ldots, b_m$，求 $a$ 中有多少长度为 $m$ 的子区间满足对应位置全都不小于 $b$ 的对应位置。

类似 bitset 加速字符串匹配的类型，由大到小枚举 $b$ 中的元素，用一个 bitset 表示 $a$ 中不小于该元素的位置，这样 bitset 的变化量是 $O(n)$ 的，总时间复杂度 $O\left(\dfrac {nm}w \right)$。