#include <Seter> - using namespace Orz;

2179: FFT快速傅立叶

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
175346	Seter	2179	Accepted	1756 kb	1120 ms	C/Edit	1597 B	2011-11-22 19:17:39

于是花了3个小时写了个分治版的大数乘法……压9位后常数果然巨小，60000位时比FFT还快一点！膜拜AC大神208MS稳居榜首！

用FFT过掉后看到TIM是用分治的……于是回去想了好久……终于想出来了……

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
174521	Seter	1861	Accepted	4588 kb	624 ms	C/Edit	2408 B	2011-11-18 20:37:53

一开始写这道题的时候总觉得自己的Splay模板的Join和Remove操作有问题……然后弄了半天各种WA囧，最后发现是题中的Insert操作交换时没更新指针……不过原来的Splay模板还真的有问题……Remove后可能存在未update的节点……改好就A了……

全完了……OI再见，文化课去了。

~~明天就是NOIp Day1了……~~

~~两年的希望……不要坑爹啊……~~

左偏树真是个超好写的东西！支持合并，插入，删除最小值三个操作。后两个操作都可以看成第一个操作的拓展，如删除最小值是合并根的两棵子树，插入则直接将元素看作一个左偏树——所以只要写个Merge就可以了！