noip2018 day1 t1
Old Memory
回首望去，他还是不忍直视当年那个抱着最美丽的幻想的，执意穿行金黄树林的小胖子。
他想骂他，在那个简单的时光中想着面子，幻想着不切实际的梦想这如今他都认为不简单的东西。
他想骂他，为什么不努力，为什么不脚踏实地。
但是他也是他，而他也将会成为他，老天用时间，信息不对等给他们两个开了一个玩笑。
他现在能做的只有继续吟啸，徐行，以此纪念这当年那个傻瓜，纪念他的梦想。
考场时，他在一个手就能数过来的我掌握的知识点中反复寻觅，同时根据学长讲的，但自己并未写过的知识点——分治，写了一个他认为很NB的分治。
当时的他只是过了样例，自己都不相信写的是正解。
在吉大外面的饭店中和同学徘徊，老师说过，要是学长们不努力，noip的分数就还是得在200左右徘徊，而他呢，这次似乎连一道题都不能确定AC。
老师来了，给他分享了t1的贪心，他当时脑子一震，当然，他还是对自己的分治抱有幻想。
而此刻，幻想彻底破灭，老师讲完，他没懂为什么分治不对，老师问懂没懂的时候也知识敷衍这点头。
day1,day2都结束了，发成绩了。
他只有 55 points 。25+0+0+0+30+0
有分的两题，分别是这道题，和填数游戏，他凭借着小学奥数瞎猜结论+手玩，以为能骗到50。。
此后他也放弃了这个题，他认为就算分治是个正确的算法，而自己一次也没有打过，甚至把学长教的二分当成分治，哈哈，算了吧。
此后的一年，两年这个想法一直没有挥散，结束了？noip2018结束了。
Present
2021.5.2
距离中考57days，他现在是初三。
"快快快，快tm给我测呀，别一直running on test 1，靠Wa on test 6了"。
又是一场4切的SB div2。
“为什么题解长得都一样？”（有的是差不多）
“为什么题解的代码也都长一样？”
“妈的，原来是个转载的，转载有个屁用。”
“妈的，都是借鉴一个人的思路。”
他才意识到，原来 "Wa on test 6" 是因为他少判断了一种情况，甚至他将这个特判的代码全部删掉也能对。
“这不就是个怪缝合题？”
他才想起来，这个似乎就是 noip day1 t1的一个增强版（缝合版）。
这道题题解给的是什么？我写的是什么？是tm的分治！！！！！！！！！！！！！！
这两年，他变了很多，他会了很多，也不甘于只听别人的解法。
他重新想了以下，发现 noip day1 t1 也是可以类似做的。
他考场上写的是正解。
他应该早早就有能力发现这点。
他应该早早的想一想，改一改题，而不是听别人分享他们自己的贪心，人类智慧。
他不应该只有55 points 。
Solution
这个题可以分治。
我们发现这个区间越长，就一定比短的优。
就最初的那段区间来说，我们最多有 \(Min_{i=1}^{r}d_i\) 次覆盖整个区间的方法。
接下来会产生一个 0，而如果把 0 当作分割符，我们的区间被分成两个区间。
而不管我们减了多少，这个一段区间内的大小关系是不会变的，我们只需要找出每个区间原先的 \(Min(d)\) 即可。
这个直接 \(st\) 表做 。
考虑复杂度，我们每找一次 \(Min(d)\) 我们就会删除一个数（变为0)，我们顶多会删除 \(n\) 次。
所以复杂度为 \(\mathcal O(n\times findmin)\) ，由于是 \(st\) 表，\(\mathcal O(n\log n+n)\)。
我现在其实特别想找出那个
JL-Senior.zip（也不知道是不是这个名字，反正CSP是这个名字）存着选手代码的zip
。
我想找出自己当年怎么写的，看能不能帮自己改一改代码，
有点懊悔自己当时得过且过，有点惋惜自己没好好学习，但这都是苍白的，因为时间已经流逝。
既然选择这般独木桥，这条人迹罕至的小路，就不能懊悔年少的无知，年少的轻狂。
做下去永远比说下去难得多。
以此，纪念那个13岁的傻瓜。