一个序列，多组询问，每次询问给出 $l$ 和 $q$，问：

$$
\sum_{i=l}^{l+q-1}\max_{l\le j\le i}a_j
$$

强制在线。

$1\le n,m\le 5\cdot 10^5$

你是否曾遇到过记不住密码的尴尬？

你是否曾担心密码过于简单而导致被轻松破解？

最近装上了Pypy，结果发现pip却装不上去了…

什么是 $NTT$

就是把把 $FFT$ 中所有的单位根换成了整数的单位根，也就是原根的 $n$ 次幂

通常用于求模意义下的多项式卷积

在上一篇文章里面我们介绍了 $FFT/IFFT$ 的基本原理和应用，今天我们来了解一下 $FFT$ 在字符串匹配中的神奇应用

引入问题

什么是多项式卷积

假设我们现在有多项式 $f(x)$ 和 $g(x)$ ，它可以被表示为

$$
f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i\\
g(x)=\sum_{i=0}^{m-1} b_i\cdot x^i
$$

其中 $a$ 和 $b$ 为系数数组， $n$ 和 $m$ 分别为两个多项式的长度

那么它们的卷积为

$$
f(x)\bigotimes g(x)=\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i\cdot b_j\cdot x^{i+j}
$$

也可以表示成

$$
c_k=\sum_{i=0}^ka_i\cdot b_{k-i}
$$

其实就是简单的两个多项式相乘

鉴于机房最近发生了一些扰乱人心的事件……

所以FGamer诞生了！

最近发现Linux中居然没有pause命令…于是在查阅了教程后，自己用C写了一个

今天也是Mivik被智商碾压的一天啊QwQ

分数规划 貌似 和01规划是一个东西吧QwQ

问题

我们现在要求这样一个式子的最大值

$$
\frac{\sum e_i.a}{\sum e_i.b}
$$

其中 $e$ 中的元素是可以选择的，且 $e_i.a > 0$ ，$ e_i.b > 0$