qoj #8602 题解 最后更新于 2025-05-01 19:05:44

题源：[qoj #8602](https://qoj.ac/problem/8602) 模拟赛里搬的题，这个原题全是俄文看不懂。 --- 简述一下题意： 对于正整数序列 $b_1,b_2,\dots,b_m$，和一个初始为 $0$ 的变量 $x$ 可以进行两种操作： 1. 令 $x\leftarrow x+1$。 2. 任选一个 $1\leq i\leq m$，令 $b_i\leftarrow b_i\oplus x$（按位异或）。 定义 $f(b[1,2,\dots,m])$ 为使得 $\forall 1\leq i\leq n,b_i=0$ 的最小操作总次数。 现在给定正整数序列 $a_1,a_2,\dots,a_n$，$Q$ 次**在线**询问给定 $l,r$ 求 $f(a[l,l+1,\dots,r])$ 的值。 --- 首先考虑 $Q=1$ 时怎么求答案。设 $k=\lfloor\log_2(max_{i=l}^r{a_i})\rfloor$，那么最后的 $x$ 一定不小于 $2^k$，否则无法消去最大值的最高位。那么如果最终加到了 $X$，第一种操作进行了 $X$ 次。对于 $a_i\leq X$，第二种操作只需要在 $x=a_i$ 时进行一次；对于 $a_i>X$，第二种操作需要在 $x=2^k$ 和 $x=(2^k\oplus a_i)<2^k$ 时各操作一次，故答案为 $\min_{X\geq 2^k}\{(r-l+1)+X+\#\{a_i|a_i>X\}\}$。这里 $\#S$ 表示集合 $S$ 中的元素个数。 这样就有一个 $O(Qn\log n)$ 的做法。 观察到我们要求的 $\min_{X\geq 2^k}\{X+\#\{a_i|a_i>X\}\}$ 只和区间内 $[2^k,2^{k+1})$ 中的 $a_i$ 有关，所以可以将序列按二进制位数拆成 $\log$ 个序列，然后分别减去 $2^k$。 那么现在问题变成了求 $min_{X\geq 0}\{X+\#\{a_i|i\in[l,r],a_i>X\}\}$。注意到 $X=0$ 时这个值是 $r-l+1$，所以 $X\leq r-l+1$。再转化一下 $min_{X\geq 0}\{X+\#\{a_i|i\in[l,r],a_i>X\}\}=r-l+1+min_{X\geq 0}\{X-\#\{a_i|a_i\leq X\}\}=r-l+1-max_{X\geq 0}\{\#\{a_i|a_i\leq X\}-X\}$，由于 $X\leq r-l+1$，只需要考虑所有不超过 $r-l+1$ 的 $a$，也就是可以认为 $a$ 的值域是 $n$。 现在要求的就是 $max_{X\geq 0}\{\#\{a_i|a_i\leq X\}-X\}$，这形式类似于 Hall 定理，可以联想到 Hall 定理（的扩展）： - 对于左部点集大小为 $n$ 的二分图，设左部点子集 $S$ 在右部中相邻的点集为 $N(S)$，那么最大匹配即为 $n-\max_S\{|S|-|N(S)|\}$。 那么现在我们可以构造一个二分图，左部点集为 $\{a_i\}$，右部点集为 ${1,2,\dots,n}$，边集为 $\{(a_i,j)|a_i\geq j\}$，那么考虑 Hall 定理的时候，我们只需要考虑所有 $S=\{a_i|a_i\leq X\}$，因为这个时候限制最严，那么 $r-l+1-max_{X\geq 0}\{\#\{a_i|a_i\leq X\}-X\}$ 就是二分图的匹配数。 这个二分图的性质很好，肯定可以贪心求最大匹配。事实上，存在一个非常好的贪心：以**任意顺序**加入左部点，在加入一个 $a$ 时，找到右部点中最大的 $x$，满足 $x$ 还不在匹配中且 $a\geq x$，将 $(a,x)$ 加入匹配。 回到原问题，先考虑离线情况，并设计一个询问复杂度较小的算法。 区间问题考虑扫描线，将所有右端点为 $r$ 的询问一起处理。那么可以依次往左部点中加入 $a_r,a_{r-1},\dots,a_1$，并用并查集维护右部未匹配的点。复杂度 $O(n^2+Q)$。 优化扫描线复杂度。首先注意到上面的贪心是不会让左部已经匹配的点失配，所以可以直接维护加入 $a_r,a_{r-1},\dots,a_1$ 后的左部匹配点集，那么查询就是查询这个点集中下标在 $[l,r]$ 中的数量。 这看似是更复杂了，但是这说明加入左部点的过程不重要，只需要知道最后匹配中的左部点集就可以了。对于右端点为 $r-1$ 的情况，左部点中依次加入了 $a_{r-1},a_{r-2},\dots$，那么对于右端点为 $r$ 的情况，实际上相当于加入了一个匹配优先级最高的 $a_r$。也就是直接强制 $a_r$ 和右部点 $x=a_r$ 匹配。这显然至多导致一个左部点失配，只需要找到这个点或者确定这个点不存在，然后用线段树维护区间和即可。 一个想法是从 $x$ 开始找增广路退流，并用数据结构维护这个过程，但这太复杂了，如果有不用维护图的形态的做法就更好了。 还是考虑 Hall 定理，对于所有左部点子集 $S_i=\{a_j|a_j\leq i\}$，维护 $c_i=i-\#\{a_j\leq i\}$，那么最大匹配就是删掉尽可能少的 $a$，使得 $\forall i,c_i\geq 0$。现在加入一个 $a_r$，可能会导致一些 $c_i<0$。那么找到最小的这个 $i$，必须要删去一个 $a_j\leq i$ 才能使得 $c_i\geq 0$。根据上面的贪心，这个 $a_j$ 应该是满足 $a_j\leq i$ 且 $j$ 最小的。 分别用一个线段树维护 $c$ 和还没被删去的 $a$，就可以做到 $O((n+Q)\log n)$。 只需要将维护 $a$ 的线段树持久化做到在线回答。 总复杂度 $O((n+Q)(\log n+\log V))$，其中 $V=2^{60}$ 是值域，有没有 $\log V$ 取决于实现。 [提交记录](https://qoj.ac/submission/997279)