BZOJ - #include <Seter> - using namespace Orz;

2007: [Noi2010]海拔

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
177134	Seter	2007	Accepted	25752 kb	200 ms	C/Edit	1288 B	2011-12-12 20:41:23

很久以前就会做了……但是因为听说卡了SPFA所以一直拖着（C党没有heap的STL真是个悲剧！）然后前几天终于准备A这题了……先写了个SPFA，各种SB，交到TYVJ上结果TLE一个点，然而奇葩的是，加了fread的的读入优化后居然TLE两个点……

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
176421	Seter	2120	Accepted	12076 kb	812 ms	C/Edit	2912 B	2011-12-02 12:44:43

10000个数，10000个操作。每次修改一个数/询问一段区间内不同的数有几个。

有点难想……树状数组~~线段树~~套平衡树。每个数第一次出现时随便改成一个负数（我改成了这个数的相反数以避免重值），之后改成前一次出现的位置。询问的时候查找一个区间中比左端点小的数有几个（就是没有前继/是区间中第一次出现的数的个数）。

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了……