U 群常见根号题汇总

如果有一些细节不懂或还有一些其他的题，可以在下面评论或私信我。

1. 区间加，区间 kth

我不会，见 zak 博客。

类似末日三问，考虑以 B 为块长进行分块。

每个块开一棵线段树，每个节点维护这个区间 (a_i+x) 乘积的多项式，pushup 就把两个儿子的多项式卷起来。

散块暴力，对于相邻两次块重构间的所有询问，我们做一个多点求值，这部分是 O(\dfrac{nm\log^2 n}B) 的。

散块修改就在块内线段树做区间修改，递归到的终止节点做一次多项式平移，然后打一个区间加的 \text{tag}，这部分是 O(mB\log n) 的。

总时间复杂度 O(\dfrac{nm\log^2 n}B+mB\log n)，B 取 \sqrt{n\log n} 即可做到 O(m\sqrt n\log^{1.5} n)。

考虑以 B 为块长进行操作序列分块，散块对散块只需做一个 exgcd，这部分是 O(mB\log n) 的。

整块对散块可以转为下面这两个子问题：

以 L 为阈值进行根号分治，对 x>L 的暴力，这部分是 O(\dfrac{nm}L) 的。

对于 x\le L 的，一次操作相当于加 \dfrac{kz^y}{1-z^x}，于是可以转为求 \sum\limits_{k=1}^L\dfrac{f_k}{1-z^k}。

分治卷积做一下就是 O(L^2\log^2 n+n\log n)。

总时间复杂度 O(\dfrac{nm}L+L^2\log^2 n+n\log n)，L 取 \dfrac{\sqrt[3]{nm}}{\log^{\frac 23} n} 即可做到 O((nm\log n)^{\frac 23})。

直接把上一问的做法转置即可，时间复杂度 O((nm\log n)^{\frac 23})。

然后考虑原问题，直接套上两问时间复杂度即 O(mB\log n+\dfrac{nm}L+\dfrac{L^2m\log^2 n}B+\dfrac{nm\log n}B)。