昨天CF的题。给一个数列，每次操作要么把一个区间的末尾数字插到头部，要么询问区间内等于某个给定值的数字的个数。
显然分块可以做，也有优雅的Splay方法，但是直观的树套树也是不错的。
一般正常是线段树套平衡树，这样复杂度很容易分析，但是对于第一维空间也是动态的情况，就没法处理了。
而平衡树套平衡树最大的问题就是旋转的时候结点内套的内容没法批量修改。
于是使用不太旋转的平衡树(比如 Scapegoat tree)就是很自然的想法了。
对于这题而言，第一维用Scapegoat tree，第二维用map就可以了。
但是写起来有一个要注意的点，因为Scapegoat tree不太好delete，我是采用lasy delete的方法。
而lasy delete以后忽略空节点的size不能用作判定平衡情况，因为被delete的元素很多的时候，这样判定树的平衡性就完全不对了。
于是不包含空节点的size和包含空节点的nodeCount都要记录。
不过跑出来的速度似乎和同样用hashmap的分块差不多，虽然理论上来讲这个时间复杂度是
分类存档：默认分类
edward_mj退役经验帖
考完试了，也是时候补上退役帖了。
考虑了一阵要怎么写，鉴于本文的目的主要是希望给后来的校队成员或者想参加这个竞赛的同学一个借鉴，最后还是决定用Q&A的形式。
打ACM/ICPC有什么好处
我觉得确切而言应该问把时间花在这上面有什么好处。
- 提升算法设计/coding能力。而这直接面向IT公司的招聘
- 获奖无论在哪里都是加分点。
- 结交这个领域很优秀的人。这条有多重要，自己感受一下吧。
如果只是抱着划划水的态度参加，几乎不投入时间，我觉得上面任意一条都得不到。
我为什么要打ICPC
- 预科的时候校队选拔第4，可以说算法底子还算是好的(至少在浙大)。当时也没想太多，觉得navi，猛犸，fancy退役以后我肯定是No.1了，好像还是挺有前途的。我一直觉得，无论在哪一个领域，只要是top的，都会有很大收获。
- 上面的好处，每一条都和我想走的路关系密切。
想在这项竞赛上取得好成绩是否需要很高智商
至少就final上拿到奖牌这一点而言，我觉得不需要，记得叉姐也是抱有同样观点的。
但是充分的练习是必要的。
高中参加OI的时候，我也曾觉得会考到的内容基本都会了，剩下的看智商，听天由命了。
后来发现只是知道工具的基础应用是远远不够的。
很多时候想不出来，是因为对这些东西的理解不够深入。
而更可怕的是，你永远不知道自己是否理解得足够深入。
于是只能在不断解决新问题的过程中，加深对这些工具的理解。
如何看待有些老师会说这个竞赛“没有创新”，“做重复的工作”，“没有意思”，“就一辈子搞这种竞赛了”
这个问题是经常有学弟学妹提到的，也是我自己亲身经历过很多次的。
首先要提到的是，每个人都有自己的局限性，老师也不例外。
想象一下如果自己是老师，每天面对追求新意的科研。
然后看到一个总是在解决别人已经解决了的问题的竞赛，会不会觉得第一反应就抵触？
人考虑东西的时候总会不自觉地把自己代入到里面，我倒是觉得老师这么想是可以理解的。
武断地以自己的价值观衡量别人，难道我们自己就没做过吗？
我还是那句话，在任何一个领域，只要是做到比较top的，收获不会少。大概也没有什么领域，随便划水就能有很大收获。
人各有志，且不论这些观点是否正确，就从解决方案来看，也不见得跟着说这些话的老师做工程/研究，就比花时间在这上面好。
如何提升自己的个人实力
没啥好讲。
把codeforces，topcoder，gcj一套一套刷下来，不懂的都看题解弄会。
无论是知识面还是coding功力必定大涨。
光说不做那只能继续被殴打。
如何挑选队友
如果你是队长，而又想保证成绩的话，一定要考虑好下面几个因素：
- 大家训练的时间能不能有保证。
- 选性格好的，能交流的。比较受的更好了:)
- 选水平高的。最好不要相信什么意愿强不强烈，什么会努力之类的鬼话。除非他很年轻，否则打不过别人自然是有他自己的问题。
组队训练什么题目
先是各个regional，再是GYM靠谱的比赛刷完，然后刷opencup。
训练的强度
eternal reality一共训了90+套题。算算10个月有多少天除一下，每套5个小时，赛后还要补题。
作为队长要注意的
首先你自己要以身作则，主动补题，让队友看到你的努力。
其次，补完了要和队友主动讨论。赛后总结的时候分清楚是策略问题，还是水平问题。
水平问题不要太急，好好补就是。
策略问题一定要重视起来，总结的时候先肯定做对的事情，再讲做错的事情。
任何一个人上来就被喷都会很难受的，而且会有自己全盘做错的感觉。
对今年的第15名有什么看法
其实没拿到牌当然还是有点不甘心。
B题是我拿手的类型，但问题是两个人的代码套在一起，不知道是谁的错了。
而且题目也一反常态地难，前期就被打蒙了。
单从训final题的来看，我们队和AoD打感觉应该是7:3开。
一路训过来好像夺冠了4次吧。就连11年AoD现场夺冠的那次也踩了。
所以说到最后还是要看发挥和运气吧。当然，临危不乱的大心脏也是很重要的！
其它注意事项
- 要想打好就不要躲题。老老实实补掉。总是只做自己会的，效果可能并不是那么好。
- 训练选题要选那些board真实的。比如regional之类的。我个人是很讨厌训那种有人贴代码的online比赛的。那种你训出来也不知道自己打得怎么样。
ACM/ICPC 2014 World Finals —— 退役战
sigh，到最后还是没有拿到奖牌，不过好歹刷进了第一版。
第15也不错了。
说说过程吧。
开场大家看题，肚子白ABCD，我EFGH，猛犸IJKL，看了好一阵，没有一题会做……
然后猛犸跟我讲了K的题意，我知道不是圈的怎么做，感觉圈的肯定是类似的，在那个做法上改，结果想了好久都没想出来。清华一下就秒了，有点欲哭无泪。这显然这是个原题，但是我们却不会做，当时就感觉不妙。
我和猛犸轮流想K，还是不会。
有人也过D了，猛犸就问肚子白题意，弄了一下终于有题会做了，令人感动。 D 55min 2Y
C也有人过，肚子白开C，调了好久，sample也不对，好不容易调对了，一交又是好几个WA……
猛犸只得又跑去看，我在G和K中交替想，终于发现我K题想的方向根本是不对的，告诉了猛犸这个题的关键：每个区间的后继是固定的。然后终于想清楚了，猛犸问我写还是他写，我觉得G我还可以想一下，I裸平面最大团有人过感觉也可以上去乱搜一发，于是觉得猛犸上比较科学。于是猛犸想了一会儿直接就过了。K 127 min 2Y
其实我觉得K题还是挺难的……但是navi说是东京大学校赛的原题，USACO据闻也有，于是就被万人轮了……我们没做过智商又一下子没上线，只好被碾压了。
期间我I写完了，交了一发TLE，顿感没救。
猛犸又去写了一半B，然后说复杂度好像不太对，跟我讲了复杂度不对的部分，让我去想。
我弄了一下，发现这就是多重背包的凸优化。正确做法是用dp中的重量对“当前物品重量”取模分剩余类，然后每个剩余类的转移利用决策单调构建单调队列来做。有点讽刺的是，这是dd的背包九讲里，唯一没有讲的多重背包的姿势。
虽然我会做，但是那个单调队列的维护需要推的公式很复杂，我推错好几次……
因为这个题除了这个离散的部分，后面还有连续的部分，我的代码和猛犸的代码套在一起，也不知道是谁的错了，怎么交都Wrong Answer。
期间我的部分发现的几个错误，猛犸的部分本来说没问题的，结果又被肚子白发现了几个致命的错误，改来改去也没见过。
然后猛犸和肚子白就去想E了，想了一会儿想出了科学的方法，封榜后1min就过了 E 241 min 1Y
这时候，猛犸选择了去改我的I看能不能搜过去，我弄了好一会儿也没弄对B，于是就跟肚子白讲。然后肚子白大概没怎么接触过这种姿势，好像也没怎么听懂。然后我发现我有一个正负号搞反了，改了以后还是无尽的WA。
然后比赛就结束了。
最后B也不知道是我的代码有问题，还是猛犸的代码有问题。
I搜不搜的过去只能看脸……中国队里也只有北大脸好搜过去了。
如果猛犸过了E以后，和我一起折腾B的话，我觉得九成就5题了，这样第10就有铜牌了(前12有奖牌)。还是有点太贪了。
当然也不怪猛犸，毕竟I也是有可能搜过去的，只能说结果是我们都悲剧了。
于是就这样在大三和FQW，GXX一起退役了，也许后面会补一个退役贴吧，不过现在得用力准备回去连续5天的考试了T_T
说实话，这两年final打下来，真是挺伤的，上一年final刚好是考试周，一坨考试都缓考了。
今年是考试周之前，回来就连考5门，= =b只能求老师们尽可能手下留情了……
2014北京邀请赛 Prob G Great Escape
做了才知道为什么NowOrNever交那么多次都没过……
首先应该要想到的做法是给每个楼之间的区间分配飞多少层楼的高度。
然后很直接的想法就是每次取涨一层楼代价最小的那个区间来加一的高度，直到这个涨的代价大于1.0/w，或者涨满L这么高。
但是L有10^9，这样做肯定是要TLE的。那么我们可以二分这个+1的代价，然后贪心地去算，然后判断楼层是否超过L就可以了。
不过我的做法更暴力一点，先直接按连续的去做了，差分变成求导，求导以后不难看出这个导数是单调递增的，由于函数是连续的，可以避免很多取整、讨论。于是通过实数的模型可以得到每个区间占用楼层的近似初值。有了这个近似初值，就可以用上面最直接的那个想法通过这道题目。不难证明复杂度是 n lg n的。
