对于可持久化的一个离线做法的IDER（毒瘤出题人都会强制在线吧）

QWQ

本着不想流失想法的态度写了这篇博客。

看下面这道题目：

对于两个长度为n（最高项为n-1）的多项式A，B，求出相乘后的C的DFT数组

有m次修改：
第i次操作有三个整数：a,b,c
表示用第a个时间点修改第b位为c
然后输出C的DFT数组
1<=n<=m<=1000
数组大小控制在500000以内

其实也很简单，思路绿题，实则套上FFT就是紫题了吧。

对于FFT的过程是一个nlogn的数组。

改一个数字就慢慢往上凑，那么其实就是：(1+2+4+8+...+n)

其实也就是(n)，所以修改复杂度是(O(n))的，然后可持久化卡内存？

那么因为不强制在线，只需要我们把可持久化的时间树建出来，然后DFS就行了。

因为每个点回到父亲可以用赋值再次实现，然后只会回一次，所以就是(O(nm))。

又水了一篇博客QAQ，被ZFY、ZWQ喷SB题，看样子只能拿去恶心师弟了。