ST表

另一种莫队算法的实现

$$O(n^2\log(u))$$

zkw真的快

出门左转58，双倍经验改一下比较....
话说难度一样的题一个一星，一个两星半，蜜汁尴尬.....

迷之数组大小

1A
随便玩玩基础(naive)的线段树..........

致 已被玩烂的PID1738

\begin{align*} \sum_{i=1}^\infty\prod_{j=1}^k\frac{1}{ik+j}&=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\int_0^1x^{ik+j-1}dx \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=0}^{k-1}(-1)^jC_{k-1}^j\int_0^1x^{ik+j}dx \\ &=(k-1)!\sum_{i=1}^\infty\int_0^1(1-x)^{k-1}x^{ik}dx \\ &=(k-1)!\int_0^1\sum_{i-1}^\infty x^{ik}(1-x)^{k-1}dx \\ &=(k-1)!\int_0^1\frac{(1-x)^{k-1}}{1-x^k}dx \\ &【前方高能预警】 \\ &=k!\int_0^1\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{1-\varepsilon^j x}dx &(\varepsilon=e^{\frac{2i\pi}{k}}) \\ &=-k!\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{\varepsilon^j}\ln(1-\varepsilon^j) \\ &=-k!\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\ln(1-\varepsilon^j) \\ &【什么？你以为这就完了？图森破】 \\ &=k!\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\sum_{i=1}^\infty\frac{\varepsilon^{ij}}{i} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\varepsilon^{ij} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\varepsilon^{jl+ij} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\sum_{j=1}^{k-1}\varepsilon^{j(i+l)} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l(-1+[(i+l)\bmod{k}=0]k) \\ &=k!\sum_{i=1}^\infty\frac{1}{i}(\sum_{l=0}^{k-1}(-1)^{k-l}C_{k-1}^l+k(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}) \\ &=(k-1)!\sum_{i=1}^\infty\frac{(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}}{i} \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=\sum_{i=1}^\infty\prod_{j=1}^k\frac{1}{ik+j} \\ &【登登登！成功推回来啦！】 \end{align*} 所以问题来了，这个式子还有更简洁的结果嘛？