从今年7月ICPC final回来以后，我一直都在思考人生。但是到现在还是处于一个比较混乱的状态。写这篇东西首要目的是理清自己的思路，次要目的是希望有人能对我的误区进行指正，最后希望我的思考可以对同样在迷茫的小伙伴有一点启发吧。

在这个过程中，我大概经历了这么几个阶段：

一、在阿里A部门实习

这前面还有个故事，当初ICPC final前投实习的时候，只投了阿里和Google上海，想着怎么也挂不了。但是没想到Google投得太晚了，一面以后HR似乎去旅游了，一个月以后告诉我一面feedback不错，但是我们快招满了blabla，校招的时候直接来，这一面就当成校招的电面了。于是乎就去了阿里实习了。

然而实习阶段又分成两半。

前一半在用Java写网站后端。这部分的心理感受大致是这样的吧：

• 做的事情单调重复、琐碎
• 同事CS基础根本没有，就像语言速成班出来的一样，几乎是以排斥的态度对待没见过的技术/工具
• 文档根本没有，接口用起来各种不清不楚
• 没有给新人足够的上手资料
• 我并不想融入到这里面，真真切切的道不同不相为谋

这里面有很多事情导致了我的这个想法，但这里并不想谈，总之一段心里大多是相对比较negative的想法。

二、在阿里B部门实习

至于为什么转了部门，主要是中间8月初有一个转正面试，而这个时候我已经过了Google HC。于是就直接对HR说，HR review的时候看了我的简历，把我介绍给了另外一个主管见面。结果就有了这次转部门。说实话我心里是很感谢这位HR的。

后一半在北京的一个算法部门，主管是从Google回到阿里的。这一段还是有点意思的，从同事给的资料以及和同事的交流中学习了不少机器学习的东西。中间和乐其的学姐交流过一下。在这一段，我的想法有了很大的改变。同期8月初开了个A股的户，开始玩起了股票。当时在想的主要有这么几个事情：

• 创业要趁早
• 炒股盈利经实践真的靠谱
• 到Google工作一下，然后回来创业
• 要做什么没想好，但是做什么都比打工好
• 我不知道我想要什么，但是平平淡淡的生活不是我是想要的
• 做什么方向随意，关键是和什么人在一起

三、校招期间

当时觉得Google、Facebook进其中一间应该不成问题，于是就没有投别的了。因为同是大公司的话，其它的就没有什么可比性的样子。这段期间也见识了各公司HR的人肉水平，总是有各种奇怪的电话打来。

里面值得一提的是华为和依图。

华为是杭研所的所长和HR总裁把我拉到曲院风荷吃了顿饭。说了一通什么人不就是为了钱和面子，你列出到Google能获得什么东西，我们都提供给你。要是愿意还可以给你带一个团队。刚开始觉得带团队还是有点吸引力的，但是一细想到阿里A部门的实习经历，带的估计也只能是那种人。就再无念想了。

依图是我到现在都纠结的一个点。和他们谈了很多次。毋庸置疑，他们几个leader很有水平，理念也很对我胃口，对方也很能坚持。而我也已经认同了这家公司。更主要的是，和我见过的别的创业团队完全不一样。谈了很多，这里还是把一些主要的想法列一下，希望自己能够尽快想清楚吧。

成功到底是什么？

这个问题真的想了很久。想起了《人性的弱点》中的一句话，人做事的动机有两点：性冲动和渴望伟大。虽然这个翻译看上去就很拙劣。但是我同意想装X是人做事的一个很主要的动机。Google的”Do Cool Thing That Matter”就是对这个观点很好的诠释。所以说其实“获得很多人的认同”这一点对于绝大部分人来说都是很具有吸引力的。

但是他们也问我了，如果你有10个优点，另外一个人每天膜拜你最不以为意的一个。你什么感觉？我想了想只能回答是翔一样的感觉。

所以说单单是认同这一点，似乎确实是说不过去。那么再想深一层，这里会出现这样的结果，无非是因为觉得对方不理解你。而这种感觉造成了对对方的不认同，于是要修正一下的话，我想要的可能就是得到“我认同的人”的“认同”。

这里又涉及另外一个问题：我认同哪些人？实际上这个答案还是相对好找的，你羡慕哪些人，想成为哪些人，那就是答案吧。

但是仔细一想，这个目标是会变的。以前中学觉得拿NOI金牌保送清华好厉害。后来觉得CF TC的红人好厉害，再到后面觉得World Finals拿牌好厉害，结果是虽然没拿到，但感觉拿到的确实比我厉害，但也不是那么羡慕了。然后是还没开始找工作的时候觉得去Google、Facebook的挺厉害，后来发现好像不是太厉害的一些人也去Google、Facebook了，自己也一下子拿到了offer，于是又感觉so so了。反正现在我觉得像依图一样开一家有逼格的公司然后不断做大做强的人都挺厉害的……

至于赚钱，是必须的，但不是目的。

我觉得成功就是获得了“我认同的人”的“认同”，而不一定是达成了特定的目的。

去G社有什么好？

我是从一开始就没有想在G社待着超过两年。毫无疑问，在美国G社的生活是相对安逸的。然而这显然不是我所追求的。那么如果说开公司就是我下一步的目的，那么我所做的就应当为自己的目标服务。站在这个层面上看，去G社最大的好处是平台更大，更容易从Top-Down的角度去看，但是底下的东西就完全没有实践的机会。所以抽象来看，获得的可能就是一个视角。

然而回顾我的经历，我就不是一个喜欢从Top到Down的人。如果从数据结构的树上来看，我喜欢的是从若干叶子开始，享受那种不同的小树根并在一起融会贯通的感觉。还有一点就是，这种方式形成的树长成什么形状，是不定的。而Top-Down的话，是相对固定的。如果你用状态压缩的动态规划写过Minimum Steiner Tree的话，就会觉得这真的很形象。XD

是不是要那么着急地开始，在G社先玩玩也挺好的？

这一点是我最犹豫的，因为说不定会在G社获得什么。但是回想起在阿里实习我自己那个状态，抱着“将来不会留在这里”的心态干活的那个状态，我想想心里有点虚。那么对比实习有什么不一样呢？我觉得一是周围人可能水平都高了，二是技术氛围更好一点。但能获得什么我真没有底。

而在依图，可以用最低的成本看到一家算是靠谱的公司是怎么成长起来的。而我自己还能在里面做一些实操的尝试，用很低的成本去试错。

至于要不要这么着急，我还是怀有疑问的。我觉得去G社大概就相当于旅游，增长见识，而practice的机会就很难有了。

我想要获得什么？

因为家庭以及ICPC的原因，在我的观点里面，要成事，团队的技术、管理和组成、对大环境的大局观都很重要。那么我学的很明确，就是技术的架构和细节，人力管理，看人的能力和对大环境的了解。为什么我没有现在开始自己创业，是因为我觉得自己的这些能力还没有达到。需要找一个试错成本比较低的地方。

如果拒绝G社，怎么面对别人的看法？

实际上我从来不在意自己是不是一个某些衡量标准下优秀的人，但我觉得我自己必须是一个特别的人。Do something cool that matter. It is absolutely irony!正因为G社的这句话，我有可能不去G社了。

最坏情况是什么？

依图挂了。我开始自己干。这几年就相当于上课了。问自己一句：怕吗？答案自然是一点也不怕。

四、结论

开始工作前去北美旅游，感受一下。

要么我了了自己的玩心，要么我发现了什么值得去看的东西。

传送门

昨天CF的题。给一个数列，每次操作要么把一个区间的末尾数字插到头部，要么询问区间内等于某个给定值的数字的个数。
显然分块可以做，也有优雅的Splay方法，但是直观的树套树也是不错的。
一般正常是线段树套平衡树，这样复杂度很容易分析，但是对于第一维空间也是动态的情况，就没法处理了。
而平衡树套平衡树最大的问题就是旋转的时候结点内套的内容没法批量修改。
于是使用不太旋转的平衡树(比如 Scapegoat tree)就是很自然的想法了。
对于这题而言，第一维用Scapegoat tree，第二维用map就可以了。
但是写起来有一个要注意的点，因为Scapegoat tree不太好delete，我是采用lasy delete的方法。
而lasy delete以后忽略空节点的size不能用作判定平衡情况，因为被delete的元素很多的时候，这样判定树的平衡性就完全不对了。
于是不包含空节点的size和包含空节点的nodeCount都要记录。
不过跑出来的速度似乎和同样用hashmap的分块差不多，虽然理论上来讲这个时间复杂度是，分块是 的。

code

考完试了，也是时候补上退役帖了。

考虑了一阵要怎么写，鉴于本文的目的主要是希望给后来的校队成员或者想参加这个竞赛的同学一个借鉴，最后还是决定用Q&A的形式。

打ACM/ICPC有什么好处

我觉得确切而言应该问把时间花在这上面有什么好处。

1. 提升算法设计/coding能力。而这直接面向IT公司的招聘
2. 获奖无论在哪里都是加分点。
3. 结交这个领域很优秀的人。这条有多重要，自己感受一下吧。

如果只是抱着划划水的态度参加，几乎不投入时间，我觉得上面任意一条都得不到。

我为什么要打ICPC

1. 预科的时候校队选拔第4，可以说算法底子还算是好的(至少在浙大)。当时也没想太多，觉得navi，猛犸，fancy退役以后我肯定是No.1了，好像还是挺有前途的。我一直觉得，无论在哪一个领域，只要是top的，都会有很大收获。
2. 上面的好处，每一条都和我想走的路关系密切。

想在这项竞赛上取得好成绩是否需要很高智商

至少就final上拿到奖牌这一点而言，我觉得不需要，记得叉姐也是抱有同样观点的。
但是充分的练习是必要的。
高中参加OI的时候，我也曾觉得会考到的内容基本都会了，剩下的看智商，听天由命了。
后来发现只是知道工具的基础应用是远远不够的。
很多时候想不出来，是因为对这些东西的理解不够深入。
而更可怕的是，你永远不知道自己是否理解得足够深入。
于是只能在不断解决新问题的过程中，加深对这些工具的理解。

如何看待有些老师会说这个竞赛“没有创新”，“做重复的工作”，“没有意思”，“就一辈子搞这种竞赛了”

这个问题是经常有学弟学妹提到的，也是我自己亲身经历过很多次的。
首先要提到的是，每个人都有自己的局限性，老师也不例外。
想象一下如果自己是老师，每天面对追求新意的科研。
然后看到一个总是在解决别人已经解决了的问题的竞赛，会不会觉得第一反应就抵触？
人考虑东西的时候总会不自觉地把自己代入到里面，我倒是觉得老师这么想是可以理解的。
武断地以自己的价值观衡量别人，难道我们自己就没做过吗？
我还是那句话，在任何一个领域，只要是做到比较top的，收获不会少。大概也没有什么领域，随便划水就能有很大收获。
人各有志，且不论这些观点是否正确，就从解决方案来看，也不见得跟着说这些话的老师做工程/研究，就比花时间在这上面好。

如何提升自己的个人实力

没啥好讲。
把codeforces，topcoder，gcj一套一套刷下来，不懂的都看题解弄会。
无论是知识面还是coding功力必定大涨。
光说不做那只能继续被殴打。

如何挑选队友

如果你是队长，而又想保证成绩的话，一定要考虑好下面几个因素：

1. 大家训练的时间能不能有保证。
2. 选性格好的，能交流的。比较受的更好了:)
3. 选水平高的。最好不要相信什么意愿强不强烈，什么会努力之类的鬼话。除非他很年轻，否则打不过别人自然是有他自己的问题。

组队训练什么题目

先是各个regional，再是GYM靠谱的比赛刷完，然后刷opencup。

训练的强度

eternal reality一共训了90+套题。算算10个月有多少天除一下，每套5个小时，赛后还要补题。

作为队长要注意的

首先你自己要以身作则，主动补题，让队友看到你的努力。
其次，补完了要和队友主动讨论。赛后总结的时候分清楚是策略问题，还是水平问题。
水平问题不要太急，好好补就是。
策略问题一定要重视起来，总结的时候先肯定做对的事情，再讲做错的事情。
任何一个人上来就被喷都会很难受的，而且会有自己全盘做错的感觉。

对今年的第15名有什么看法

其实没拿到牌当然还是有点不甘心。
B题是我拿手的类型，但问题是两个人的代码套在一起，不知道是谁的错了。
而且题目也一反常态地难，前期就被打蒙了。
单从训final题的来看，我们队和AoD打感觉应该是7:3开。
一路训过来好像夺冠了4次吧。就连11年AoD现场夺冠的那次也踩了。
所以说到最后还是要看发挥和运气吧。当然，临危不乱的大心脏也是很重要的！

其它注意事项

1. 要想打好就不要躲题。老老实实补掉。总是只做自己会的，效果可能并不是那么好。
2. 训练选题要选那些board真实的。比如regional之类的。我个人是很讨厌训那种有人贴代码的online比赛的。那种你训出来也不知道自己打得怎么样。