题面

给定 $2n$ 个线段 $[l_i,r_i]$ $(1 \le i \le n)$ 和 $[s_i,t_i]$ $(1 \le i \le n)$,对于所有排列 $p$ 求 $\bigcup_{i=1}^{n} [l_i,r_i] \times [s_{p_i}, t_{p_i}]$ (面积并)之和。其中 $1 \le n \le 2 \times 10^5$。

分析

拆开来算贡献。

对于第一维($x$ 轴),将其通过左闭右开区间离散化为小块。假设每块被覆盖了 $s_i$ 次,也就意味着这一个块对应了 $s_i$ 个 $y$ 轴线段。比如说,$s_i=0$,那么上面没有任何线段;$s_i=1$,对应了 $1$ 个线段,也就是所有线段均有可能竖着放在它上面,对答案的总贡献为所有线段的总长度;类似地,$s_i=2$ 就是枚举一对线段计算贡献之和。

可以发现,对于每一个小块只有参数 $s_i$ 有效。于是,我们将问题转化为了一个一维的问题,即对于从线段集合中选择 $k=0,1,\dots,n$ 条线段产生的总贡献,形式化地 $f(k)=\sum_{S \subseteq U, |S|=k} |\bigcup_{i \in S} [s_i, t_i]|$。

再拆开来算一次贡献,同样离散化。假设每块被覆盖了 $s_i$ 次,这个块产生贡献当且仅当选出的 $k$ 个块包含 $s_i$ 中的某一个,即方案数就是 $\binom{n}{k} - \binom{n-s_i}{k}$,对于贡献还要乘上块的长度。观察上面的式子,第一部分是平凡的,关键是第二部分,因为我们最终计算的是 $f(k)$ 每个点的值,因此同样的 $n-s_i$ 产生的长度贡献可以记录在一起。于是,我们定义这部分的贡献函数 $g(k)=\sum_{i=k}^n a_i C(i,k)$,其中 $a_i$ 就是长度和。

将 $g$ 展开

$$
\begin{eqnarray}
g(k) & = & \sum_{i = k}^n a_i \frac{i!}{k!(i-k)!} \
g(k) & = & \frac{1}{k!} \sum_{i = k}^{n} (a_i \cdot i!) \times \frac{1}{(i-k)!}
\end{eqnarray}
$$

注意到上式的下标分别为 $i$ 和 $i-k$,即差为定值 $k$,使用 FFT 计算即可。

最后,还有一点小问题,$f(k)$ 的贡献是无序的。它表示从第二个集合中选择了 $k$ 条线段去和横轴某一小块的 $k$ 次覆盖对应,剩余随便,也就是需要乘上两部分内部的排列,即 $k! \times (n-k)!$。

阅读全文 »

题面

给定一个长度为 $10^5$ 的字符串,求同构意义下的本质不同子串数。

分析

考虑如何求一个串的本质不同子串数,实际上对他求一个后缀数组和 height 数组即可,进一步转化我们只要能对求出两个后缀的 LCP 长度,就能实现后缀排序。

将同构转化为距离上一次出现该字符的距离,可以发现每个后缀和整体的差别仅有 $26$ 个开始位置。

我们现在考虑如何求两个后缀的 LCP,首先两个字符的情况可以参考 2020 牛客暑期多校训练营第 1 场 A,我们将其扩展到更大字符集。

aaababccabdb

我们将这个串,用每种字符的第一次出现位置分割开来。如果两个串同构,那么这些位置必然也是一一对应相同的。

求 LCP 时,只需要一段一段考虑即可。

阅读全文 »

题面

给定一个长度为 $n$ 的数组,对于所有子数组求最大子段和。

其中 $2 \le n \le 10^5$。

分析

考虑分治,也就是需要统计跨越中点 $m$ 的贡献。

注意到,跨越中点的区间的最大子段和位置,它要么完全在左半边,要么完全在右半边,要么是中点往左右延申得到的。

我们在区间 $[l,m]$ 枚举左端点的位置,可以发现右端点从左往右移动的过程中:首先是一段使用完全在左半边,然后是一段左右拼接,最后是完全在右半边。

二分出 $2$ 个边界的位置即可。

阅读全文 »

题面

给定一棵 $n$ 个点的有根树,初始时,每个点处于上班状态,你现在需要构造一个操作序列,使得每个点都满足一次,一个点满足当且仅当只有这个点的子树在上班,其他全在下班。

操作序列会维护一个栈结构,分为 $3$ 种操作:

  1. 点 $u$ 下班,加入栈中;

  2. 栈顶 $u$ 弹栈,$u$ 重新上班;

  3. 报告点 $u$ 处于满足状态。

其中 $2 \le n \le 10^5$,操作序列长度不超过 $9 \times 10^6$。

分析

对于一棵大小为 $n$ 的树,我们可以选择一条链(不妨选择重链),不断将外部的点删掉,可以用 $n$ 次操作,由浅到深将整条链都满足一次。之后,这条链就不在有用了,并且把树划分为一个森林,有多个等价的子问题。

思考一些暴力的做法,留下一棵树,其他入栈,对这棵树递归构造完成后(递归后满足子树所有点在栈中),需要去弹出下一个子问题的树,因为是栈结构,所以需要弹出栈顶的两棵树,再将做好的树入栈,以此类推。显然,这样一开始做的树就会被反复加入和弹出,不够优。

不妨使用哈夫曼编码以子树的大小作为频率值进行合并,在构造好的哈夫曼树上递归构造即可。由于哈夫曼编码的性质,每个点深度频率乘积的和,大约为 $O(n \log n)$ 级别,可以通过本题。

阅读全文 »

A Circle Coloring

每个点有 $3$ 种选择,一个点需要与前后不同,显然遍历一遍即可。

B Arrays Sum

注意到,每种数有多个并没有用,假设一共有 $n$ 种数。

考虑 $k=2$ 的时候情况,如果 $n \le 2$,那么一次操作就能完成,否则之后每次前面一部分填 $0$,然后构造下一个数。

因此 $k>2$ 也是类似的,第一步制造 $k$ 个,然后每次制造 $k-1$。

C Discrete Acceleration

直接对着题意模拟即可。

D Searchlights

注意到,被控制的区域呈现一种下降台阶的形状。于是,每个人,要么往上走,要么往右走,要么走到某个拐角处。

于是,每个人有很多种选择 $(x_j,y_j)$,表示他两个方向需要的步数。

按 $x$ 从小到大枚举,如果所有人都满足过了,在所有人 $y$ 的最小值,取最大值。

E Avoid Rainbow Cycles

注意到,对于每个集合,不需要真的搞出最大团,只要按顺序连成一条链,如果这个图有环,那么原图必有环。

因此题目要求的是,删除最小的边,使得原图没有环,也就是加入最多的树边。

做一个类似 MST 的过程即可。

F Two Different

考虑 $n=2^k$,我们可以每次将数组对半分,如果左右半边都分别被弄成了同样的数,那么我们通过左右两边一一对应,就能将整个区间弄成同一个数。

进一步,考虑 $n$ 的最高位,类似 ST 表,做两次即可。

G Clusterization Counting

给定一个无向带权完全图,每条边边权不同,求有多少种点集的划分方案,使得每个团内的所有边权小于该团所有向外的出边。

观察 Kruskal 建最小生成树的过程,每次合并两个连通块,新加入那条边的权值一定大于两个连通块内的所有边,于是我们可以合并两个连通块的 dp 值。

合并 dp 值只需要做一个类似卷积的过程即可。

特别地,如果某个连通块本身就是 $1$ 个团,那么其分成 $1$ 块的方案数 $+1$。

具体实现可以构造一棵 Kruskal 重构树,做树形背包的 dp

阅读全文 »