个人经历分享，仅供娱乐，为贵紫杉

某年某月某日晚上，某蒟蒻在经历了一天的颓废以后，发现自己要被地铁站区分了这辈子冇了，遂打开CF，开了一把$3 \times 10^8$人的枪战梦想 开了一个大水题。蒟蒻原本以为这是改善自己颓废现状的起点，是提升自己水平，向传奇CF选手地铁站看齐的第一步，但是没想到这道水题却硬控了蒟蒻一个晚上，在Wonderful Answer和Time Limit Enough的路上焊死车门，拆掉刹车，油门踩到油缸里，一路狂奔。 读完那机翻的题面，再打开画图工具对着样例一顿霍霍，一个初步的想法浮现在蒟蒻脑海中。拿一个猫踢set来计数(划重点，后面要考)，用双指针正着扫一遍，然后把序列reverse，再用双指针扫一遍，不出十几分钟蒟蒻写出了初步的代码，又过了小的样例，提交上去惨遭Wonderful Answer。

看完那个错误的信息，蒟蒻发现是一个貌似corner case的情况没有处理到，于是就加了特判，可是再次提交依旧wonderful answer。

蒟蒻此时已经对这道题失去了耐心，于是恬不知耻的打开了记录页面，筛选了dalao们的ac记录。看着dalao那高深莫测的代码，写法上和蒟蒻的史山有很大差异，蒟蒻决定拿出珍藏已久的对拍器，拍了几个小的数据就把蒟蒻代码的问题暴露出来：有一种情况没有考虑，需要再加分讨，虽然看不懂dalao是如何实现这个的，但是蒟蒻还是掏出了两个猫踢set，然后扫了一遍数组，把这个问题解决了。

提交，Running on test 23，蒟蒻觉得自己终于把这个题解决了，于是又去题库找了又一道水题。可是刷新了几次，状态却一直卡在test 23，蒟蒻心里突然有了一种不妙的预感。

啊？怎么还会Time Limit Enough呢?为什么呢？

打开评测记录（当然又被your browser is being checked.it will take a few seconds卡了一会），蒟蒻发现被一个$N=10^6$的点卡住了。在本地造了$N=10^6$的数据，发现跑的超级久。是常数大了，还是复杂度fAKe了？

答案就是——已经反复暗示过的——猫踢set！

原因就是：蒟蒻使用了猫踢set的count函数来统计容器中是否存在指定的元素。但是猫踢set的count复杂度是$O(logN +cnt)$，其中$N$为容器大小，$cnt$是查找的元素在容器中重复的个数。当猫踢set中有很多很多相同的元素的时候，count的复杂度就会变得很大，于是就使得蒟蒻的程序fAKe了。可是蒟蒻是蒟蒻，怎么会知道败在了一个小小的猫踢set上呢？

于是解决方案也就呼之欲出：干掉缓慢的猫踢set，对值域离散化，然后再使用桶统计。sort，unique，lower_bound，一套操作下来，再开一个桶，本地测试只用了500毫秒就跑过了1e6，而题目时限给到了2秒。

这回......大概......应该能过了吧？

蒟蒻信心满满地再次提交，差点忘了删freopen，结果依旧,Time Limit Enough on test 23。

复杂度没问题，那应该是常数太太太大了吧。蒟蒻一边谴责着CF的评测姬跑的太慢，一边进一步的卡常甚至丧心病狂地#pragma了一个Ofast以后，本地只要63.75ms就能过1e6了，交上去也顺理成章的过掉了。

但是——代价是什么呢？

蒟蒻被这题整的彻夜难眠，于是爬起来写了这篇，以发泄情绪抒发情感和进食后人。