UOJ Logo Zijian Online Judge

ZOJ

#45. 锅

统计

傅里叶变换是一个经典的问题,它在数学、工程、计算机科学中都有着深刻的意义。而二十世纪十大算法之一的快速傅里叶变换 (Fast Fourier Transform, FFT) 使它改善了许多算法的运行时间,例如将多项式卷积从 $\Theta\left( n ^ {\log_2 3}\right) \approx \Theta(n^{1.585})$ 的 Karatsuba 算法变成了套用 FFT 即可 $\Theta(n\log n)$ 即可解决的问题。

在此明确傅里叶变换的定义,记 $\widehat A$ 是 $A$ 的离散傅里叶变换:

$$ \widehat A_i = \sum_{j = 0}^{n - 1} \omega_n^{ij} A_j $$

其中,$\omega_n^{k} = \mathrm{e}^{2\pi \mathrm{i}k/n}$

EI 在 OJ 上刷题练习如何写 FFT ,然而这个 OJ 的这道题比较神奇,服务器会与学生的程序进行交互,查询变换后的一部分取值,并且与标程的运行结果进行比对。

不妙的是此 OJ 时运极差,常常出锅,主要原因是太阳黑子会改变原数组的值,这样一来 FFT 后的值就会有变化,神奇的标程又能每次在 $\Theta(1)$ 的时间内重新算出 FFT 后数组的某一项。

EI 想了想,他并不知道该怎么办,他希望你来帮助一下他。

一句话题意:维护一个数组,支持单点修改,对傅里叶变换后的数组单点查值。

输入格式

第一行,输入两个正整数 $k, q$ 表示数组长度 $n = 2^k$ 和操作次数。

接下来一行 $n$ 个数表示数组的每一项 $A_i$。

接下来行,每行第一个数 $opt$ 表示操作类型,后面跟有 1 或 2 个数。

$1\ i\ x$ 表示 $A_i$ 加上 $x$。

$2\ i$ 表示查询 $\widehat A_i$ 的值。

注意:数组是从 0 开始计数的,输入的都是整数。

输出格式

对于每个询问操作,一行输出两个实数分别表示实部和虚部。

与标准答案差的绝对值不应超过 $10^{-4}$ 即可。

样例 1

input

2 9
1 3 2 -2
2 0
2 1
2 2
2 3
1 2 -1
2 0
2 1
2 2
2 3

output

4 0
-1 5
2 0
-1 -5
3 0
0 5
1 0
0 -5

限制与约束

$|A_i|, |x| \le 10$, $1 \le k \le 18$, $1 \le q \le 10^5$, $0 \le i < n$

Subtask 1 (8 pts.),$1 \le k \le 14$, $1 \le q \le 5 \times 10^4$,查询次数 $1 \le q_{\text{query}} \le 500$

Subtask 2 (14 pts.),$1 \le k \le 14$, $1 \le q \le 5 \times 10^4$,修改次数 $1 \le q_{\text{change}} \le 500$

Subtask 3 (34 pts.),$1 \le k \le 16$, $1 \le q \le 5 \times 10^4$

Subtask 4 (44 pts.),$1 \le k \le 18$, $1 \le q \le 10^5$

时间限制:$2\,\mathrm{s}$

空间限制:$256\,\mathrm{MB}$