[Mivik的萌新赛][T3 Mivik的神力] 题解
一个序列,多组询问,每次询问给出 $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$
一个序列,多组询问,每次询问给出 $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却装不上去了…
在上一篇文章里面我们介绍了 $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}
$$
其实就是简单的两个多项式相乘
最近发现Linux中居然没有pause
命令…于是在查阅了教程后,自己用C写了一个