比赛链接

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 \leq 1.5 \times 10^5$ 个数 $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)$。

Upsolved by nikkukun.

区间 $[l, r]$ 可以任意变到 $[l+1, r]$ 或 $[l, r-1]$，同时提供了 $m$ 种已有的方案，每种方案仅属于以下一种：

1. 用一些花费禁掉 $[l_i, r_i]$ 与 $[l_i+1, r_i]$ 之间的双向转化
2. 用一些花费禁掉 $[l_i, r_i]$ 与 $[l_i, r_i-1]$ 之间的双向转化

初始有区间 $[1, n]$（$n \leq 500$），你可以选择一些方案，使得任意转换过程中不出现 $l = r$ 的区间，并求最小花费。

用区间代表的二元组建成一个 $n \times n$ 的网格图，相当于禁掉一些边，使得 $(1, n)$ 不能走到 $y = x$ 的位置上。这个东西是平面图最小割，参考 狼抓兔子 跑最短路即可。