十月杂题选做

· · 个人记录

Grakn Forces 2020 题解-洛谷 Grakn Forces 2020 题解-cnblogs

code 见 A B C D E F G H I

LOJ#6101. 「2017 山东二轮集训 Day1」第二题

按照最小值分治到两边，然后直接做即可。

code 见 [my solution](https://www.cnblogs.com/s-r-f/p/13763647.html) --- [AtCoder Regular Contest 104 题解-洛谷博客](https://www.luogu.com.cn/blog/s-r-f/solution-ARC104) [AtCoder Regular Contest 104 题解-cnblogs](https://www.cnblogs.com/s-r-f/p/13766455.html) --- [洛谷P6800 【模板】Chirp-Z Transform](https://www.luogu.com.cn/problem/P6800) 补板子。 $ans_i = F(c^i) = \sum\limits_{j=0}^{n-1} a_jc^{ij}

众所周知, ij = \binom{i+j}{2} - \binom{i}{2} - \binom{j}{2} :

ans_i = c^{-\binom{i}{2}} \sum\limits_{j=0}^{n-1} a_jc^{-\binom{j}{2}} c^{\binom{i+j}{2}}

不难发现这是一个卷积形式，模数 998244353 为 NTT 模数, NTT 即可。

几个细节：

$2.$ 每次用快速幂算$c^{-\binom{i}{2}}$ 和 $c^{\binom{i}{2}}$ 是$\Theta((n+m)\log mod)$ 的,非常慢。 可以 $\Theta(\sqrt{mod})$ 预处理然后光速幂$\Theta(1)$查询,或者用两次前缀积直接递推结果. code 见 [my solution](https://www.luogu.com.cn/blog/s-r-f/solution-p6800) --- [[USACO19DEC]Milk Visits G](https://www.luogu.com.cn/problem/P5838) 利用 tarjan 求 LCA 的思想来解决问题。 考虑把询问挂在点上，然后考虑求出 x -> 根 的路径上最深的对应颜色的点以及 y -> 根 的路径上最深的对应颜色的点 ， 如果他们相等，就不满足条件；否则满足条件。 $\Theta(n+q)

洛谷P6783 【[Ynoi2008]rrusq】

离线询问，从小到大扫描右端点的同时维护左端点的答案。

记 l_i 表示第 i 个点 (i,p_i) 最晚被覆盖到的时间 .

不难发现我们需要对一个点集的 l_i 进行赋值，同时维护一个关于 l_i 的后缀和。

对点建出 KDTree , 每次询问在 KDTree 上遍历并打标记,在打标记的同时要把子树内的所有标记收回。因为收回标记对应着打标记，所以复杂度仍然是 \Theta(m) 次遍历 KDTree 的复杂度 , 即 \Theta(m\sqrt n) 次打标记/收回标记的操作。

现在我们要完成的问题变成了支持 \Theta(m\sqrt n) 次单点修改和 \Theta(m) 次后缀查询的数据结构 , 不难发现可以用 \Theta(1)-\Theta(\sqrt m) 的分块来实现它。

时间复杂度 \Theta(n\sqrt m+m\sqrt n) , 空间复杂度 \Theta(n+m)

code : 见 my solution