完美匹配(match)

给定 $n$ 个 $a_i$ 和 $m$ 个 $b_i$，要求满足 $a_i + b_j \ge S$ 且 $|a_i - b_j| \le D$ 的可以配对一次，每一个 $a_i$ 或 $b_i$ 只能配对一次，问最大配对方案。

对于特殊性质 $\text{A}$：满足 $D = 10 ^ 9$。

测试点 1 ~ 2 (20pts)

由于 $n, m \le 10$，所以，我们可以暴力的去 DFS，每次为当前的试卷找一个配对的人，时间复杂度 $\mathcal{O}(m ^n \times n)$。

实现略。

测试点 3 ~ 4 （20pts）

由于 $n, m \le 1000$，我们就可以考虑 $nm$ 的做法。

匹配的问题，不可避免的可以想到去跑二分图匹配，只要我们能把边建出来。

对于建边的过程，我们可以选择 $\mathcal{O}(nm)$ 的去判断是否可以配对，连边。

连完边之后我们就可以直接进行二分图最大匹配。而二分图最大匹配的复杂度理论是 $\mathcal{O}(nm)$，可以通过。

测试点 5 ~ 6 （20pts）

因为 $D \le 10 ^ 9$，因此对于任意的 $a_i, b_j \in [1, 10 ^ 9]$，一定有 $|a_i - b_j| \le D$，所以我们现在只有第一个条件需要看。

第一个条件很简单，就是 $a_i + b_j \ge S$。

我们要选择尽可能多的匹配。

我们可以把这个式子转化一下，那么对于 $b_i$ 来说，就是 $b_i \ge S- a_i$，我们令 $c_i = S - a_i$，那么对于每一个 $b_i$ 只有让 $c_j \le b_i$ 的时候，就可以让这个 $a_j$ 和 $b_i$ 进行配合。

那就很简单了，我们只需要把 $c_i$ 和 $b_i$ 进行升序排序，我们对于每一个 $b_i$ 可以选择最大的 $\le b_i$ 的 $c_i$，这个过程可以利用双指针，或者放一个堆。

时间复杂度 $\mathcal{O}(n \log n)$

测试点 7 ~ 10 (40pts)

实际上对于特殊性质 $A$ 来说，已经给了我们一些提示，那就可以把这个不等式进行转化：

首先是我们还是先以 $b_i$ 为主，那么就可以转化为，$b_j \ge S - a_i$，第二个不等式我们可以把绝对值拆开，左边是 $b_j \ge a_i - D$，右边就是 $b_j \le a_i + D$。

那么对于每一个 $b_j$ 来说，我们能选到的就是区间 $[\max(S - a_i , a_i - D), a_i + D]$。

因此现在的问题就变为了，现在有若干个区间，和若干个点，每一个点只能匹配一个区间，问最大的匹配数量。这是一个很经典的贪心模型，我们直接对于每一个区间按左端点排序，对于每一个 $b_j$ 也按是升序排序，我们遍历每一个 $b_i$，对于每一个 $b_i$ 来说，我们能选择的是覆盖这个点的 $r$ 最小的区间，那么这个过程我们可以直接用一个小根堆维护。

时间复杂度 $\mathcal{O}(n \log n)$

点击查看题解文档

点击查看题解文档

字符串练手题，不算太难。用字符串 $t$ 代指询问的串 $w$。

首先仔细琢磨一下，发现 $kq\le 10^5$，这启发对 $k$ 进行阈值分治，设阈值为 $B$。

对于 $k\ge B$，发现 $q$ 比较小，考虑对于每个询问，直接枚举所有 $i\in[a,b]$ 的 $[l_i,r_i]$ 来计算答案，对 $s$ 建立 SAM，并让 $t$ 的每个前缀 $t_i$ 跑出与 $s$ 子串匹配的最长后缀长度 $w_i$ 以及其对应的状态 $p_i$，若 $t_{l\sim r}$ 在 $s$ 中存在，则满足 $w_r\ge r-l+1$，对于其出现次数，只需要得到 $t_{l\sim r}$ 在 SAM 上对应的位置即可，预处理后缀树的倍增数组，跳到最后一个满足 $len_f\ge r-l+1$ 的 $p_r$ 的祖先 $f$，查询 $f$ 状态对应的 endpos 集合大小即可，预处理即可。

对于 $k<B$，注意到可以直接枚举 $t$ 的所有子串 $t_{l,r}$，并计算这个子串在 $s$ 的出现次数，同时计算区间 $[l,r]$ 在 $[a,b]$ 这个范围内出现多少次。对于前者，固定 $l$ 移动 $r$ 做匹配，匹配失败后面就直接退出，预处理后缀树的 endpos 集合大小即可计算次数，对于后者，拿 vector 存下每个区间在区间序列中出现的位置，然后二分查找计算出现次数即可。

理论复杂度可以做到 $O(n\sqrt{n\log n})$，两个部分都是，不知道能不能做到更优，实测取 $B=500$ 能过

本来还有 $30$ 分给多项式的，但是阻碍了伟大的 hxf 的 AK 之路，考虑到 CCF 不会出多项式，所以去掉了这一部分。

正难则反，考虑去算有那几步是不会产生贡献的，若第 $i$ 步不会产生贡献，则说明之前已经走到过这里一次了。

枚举第 $i$ 步所在的格子在 $t$ 步之前已经来到过这里了，设 $f_i$ 表示从一个位置出发，走 $i$ 步又回来，期间不经过这个位置的方案数。限制中间不经过是为了防止算重，求出 $f$ 后，答案为 $\sum_{i=1}^n\sum_{t=1}^if_t4^{n-t}$，不难发现这个式子和 $i$ 无关，继续化简为 $\sum_{t=1}^nf_t4^{n-t}(n-t+1)$。

问题是如何求出 $f$，考虑单步容斥，先求出 $g_i$ 表示从一个位置出发，走 $i$ 步又回来的方案数，则有 $f_i=g_i-\sum_{j=1}^{i}f_jg_{i-j}$。

对于 $g_i$，可以枚举竖直方向走了多少步，水平方向走了多少步，组合起来，通过组合恒等式可以证明当 $i$ 为偶数时，$g_i=(C_{i}^{i/2})^2$。另外一个方法是旋转坐标系 $45$ 度，无论上下左右都相当于在竖直和水平上都选择一个方向走一个单位长度，也能直接得到这个结论。

直接计算即可，瓶颈在于求 $f$，实际上可以用多项式优化，但是不是很文明所以去掉了。朴素实现是 $O(n^2)$，多项式是 $O(n\log n)$，听说存在 $O(n)$ 的做法。

双倍经验：4388. [Ynoi2019 模拟赛] Yuno loves sqrt technology I

好像还有个离线数据加强版但是我忘了题号了。

题意：强制在线查询区间 [l, r] 的众数，$n \leq 4\times 10^4$，$m \leq 5\times 10^4$。由$a_i$范围知道要离散化一下，记录每个值出现位置为$idx[x] = \{pos_1, pos_2, ..., pos_k\}$，同时如果要$O(1)$查询$j$在第$L$块到第$R$块之间的出现次数，就可以用前缀和预处理。

接着枚举起点块$i$，维护计数数组cnt，从块$i$往后逐块扩展$j$。每扩展一块，把该块所有数加入cnt，更新当前众数，记录到$p[i][j]$。

然后对于询问$[l, r]$，设$l$在块$bl$，$r$在块$br$。 如果同块或者相邻，那直接$O(2\sqrt{n})$枚举一下就完事了；如果跨块了，那就还是分成两小碎块和一大块处理。这时候发动我们的注意力：显然众数的候选区只有三个：1. 中间完整块的众数：$cand = p[bl+1][br-1]$ 2. 左零散中出现的每个数 3. 右零散中出现的每个数。这是为什么呢？显然中间完整快内其他蒲公英出现次数不可能比这几个众数还大，所以直接取中间众数，候选数最多$2B+1 \approx 401$个，每次$O(\log n)$，很舒服。

所以总复杂度预处理$O(n\sqrt{n})$，单次查询$O(\sqrt{n} \log n)$，总$O((n+m)\sqrt{n} \log n)$。很合理的一个式子。