题解_牛客博客

重新排列

一段字符串可以重新排列成喜欢的子串当且仅当“puleyaknoi”中每个字母在其中出现至少一次，考虑用双指针，当找到符合条件的右端点，更新答案，然后将左端点向右移动直到不符合要求，重复如上操作直至结束。复杂度 $O(n)$
sol

拼凑

因为不能重新排列顺序，所以要求必须是按顺序出现。考虑用基础DP， $f_{i,j}$ 表示到第i个位置，匹配到模板串第j位的最优答案。因为模式串里没有重复字符，所以转移十分容易。如果当前位置与模式串里的第k位相同，可以从 $f_{i-1,k-1}$ 转移过来，任何情况下都可以从 $f_{i-1,j}$ 继承答案，复杂度 $O(n)$
sol

Mu函数

发现一个事情，总共有两种情况：

1.进入一个1，-1交替的循环

2. $\mu(x)=0$

因为4的倍数都是0，所以有用的操作最多就4次。于是K的范围便没了太大意义。

所以剩下的部分就是快速求莫比乌斯函数了，线性筛和质因数分解均可解决问题。

质因数分解如果写的比较暴力大概率会过不去。

复杂度 $O(n+T)$

sol

数树

有个经典结论是树的 $m=n-1$ ，这对森林里每棵大小大于1的树都是成立的。所以问题只剩下维护是否有边和是否连的是重边，是否删除的是不存在的边。本质上都是维护边，开一个map存储一下即可。每次计算答案用度数大于1的点的数量减去图上的边的数量。时间复杂度 $O(nlogn)$

实际上这题可以用LCT通过，但在代码量上复杂了些。

sol

看比赛

考虑题意，有一个简单的转化：有一些长为1的不同线段，对于每个线段，选择其左端点或右端点做为关键字进行排序，求不同序列的个数。

首先我们按照左端点排序，左端点相同的按线段编号优先级，以下 $[x,y]$ 表示排序后的线段编号区间 $[x,y]$ 。

定义线段前缀 $[1,i]$ 选择端点的两种方案是不可区分的，当且仅当 $[i+1,n]$ 后缀无论使用任何选法，都不能区别开这两种取法。

记 $f[i]$ 表示 $[1,i]$ 可区分的方案数，不考虑不可区分的状态，应有 $f[i]=2f[i-1]$ 。考虑容斥掉不可区分的部分。

对于线段 $i$ ,容易发现，在按线段左端点排好序的前提下，可以找到一个 $j$ ，使得j的右端点距离i的左端点最近。也可以找到 $k$ 使得 $k$ 的左端点离着 $i$ 的右端点最近。

那么线段前缀 $[j+1,i-1]$ 全部取左端点， $[i+1,k-1]$ 全部取右端点，这样对于 $i$ 的键值取法既不可区分。

容易理解的，对于线段 $i$ 的两种取法，对线段 $k$ 处的 $f[k]$ 额外贡献了不可区分的f的方案，所以减去。可以证明这样的算法对于 $f[i]$ 是不重不漏的。

由于 $j,k$ 单调，动态规划部分复杂度为线性。所以复杂度为排序复杂度。实现非常简单，建议离散化降低特判难度。

sol

曲调

首先前缀和，然后变成求区间内求绝对值最小的两个数的差。设前缀和数组为 $A$ .

考虑离线，将询问按右端点排序。我们从小到大枚举询问区间的右端点 $r$ , 同时用数据结构维护每个左端点的答案。考虑新增一个数 $A_r$ 与它前面的点构成数对产生的贡献。

这里我们只考虑 $x\lt r$ 且 $A_x\le A_r$ 的 $x$ 与 $r$ 组成数对的贡献, 对于 $A_x\gt A_r$ 的情况反过来按同样的方法处理一遍即可。

首先我们找到最大的 $x$ 满足 $x\lt r$ 且 $A_x\le A_r$ ，记为 $x_1$ ，那么对于所有 $l\le x_1$ ，左端点为 $l$ 的询问都要与 $(A_r-A_{x_1})$ 取 $\min$ 。然后我们找到最大的 $x$ 满足 $x\lt x_1$ 且 $A_{x_1}\lt A_x\le A_r$ ，记为 $x_2$ ，那么对于所有 $l\le x_2$ ，左端点为 $l$ 的询问都要与 $(A_r-A_{x_2})$ 取 $\min$ 。就这样依次找下去，每次更新答案，直到 $A_r=A_{x_i}$ 或 $x_i=1$ 为止。

问题是，最坏情况下每个点寻找 $x$ 的次数可能达到 $O(n)$ 级别。

观察到这样一个性质：当我们寻找 $x_2$ 时，若 $A_{x_2}-A_{x_1}\le A_{r}-A_{x_2}$ , 那么数对 $(x_2,r)$ 对答案没有任何贡献，因为无论询问的区间是什么， $(x_2,x_1)$ 总比 $(x_2,r)$ 优。于是我们可以只寻找那些 $\lceil\frac{A_{x_1}+A_r}{2}\rceil\le A_{x}\le A_r$ 的最大的 $x$ 作为 $x_2$ ; 后面的也照此方法优化，每次只查询介于上一次找到的数和 $A_r$ 之间的最靠右的点。这样每次的查询值域区间 $[A_{x_i},A_r]$ 都不超过上一次的一半，总共只会有 $O(\log W)$ 次寻找 $x_i$ . ( $W$ 为 $A$ 数组的值域)

寻找 $x_i$ 可以用主席树简单维护来做到单次 $O(\log n)$ ; 区间取 $\min$ 也可以用线段树等数据结构简单维护。

时间复杂度 $O(n\log n\log W)$ .

sol