算是一些要对自己说，让自己记住的话和人生经验吧。如果碰巧能启发到其他人，那就太好了。

每个时刻都应该知道自己该干什么，并有效执行

恰逢前阵子TI6护国神翼夺冠，看到知乎上有人回答，在dota界极少有整场都知道自己该干什么并贯彻执行的。而神翼是5个人都很清楚要干什么。就像大酒神伍声视频里总是强调，打dota路人就是要每时每刻想着单位时间里收益最大的动作是什么。在为梦想拼搏的时候，也是如此。生活可以过得写意一些，但至少工作时间里，需要做到这一点。曾经有人说我目的性太强。但正是这样，才让我走到今日。恰恰相反，我不是目的性太强，而是还不够强，因为我觉得自己还没有达到这种境界。

每次只干一件事

专注非常有好处，这可能分人。就我自己而言，即使面对multi-tasking的情形，事情也是要一件一件来处理，把所有东西都打开对我自身效率的提升毫无用处。我想如何处理multi-tasking，CPU调度方式已经给了我们答案。Round-robin scheduling + priority。

生活节奏不能乱

该睡觉就睡觉，该吃饭就吃饭，该干活干活，该看书看书，该玩就玩。再也不像学生时代那样可以随便乱来了。因为如果工作了还保持这样，很可能一辈子就是这样了。Life is not a sprint, it is a marathon。仰望星空的同时，更重要的是脚踏实地，过好每一天。你仰望的星空，也许在你实力增长以后，就不再是你要的星空了。但脚踏实地带来的提升，会永远保留着。这一点上很佩服一些女孩子XD。

努力一定会有提高

这一点其实以前大学搞竞赛的时候就已经深刻体会到了。第二年打world finals和第一年打的时候比完全是处于两个境界。犹记得第一年训练结果忽好忽还，后来我甚至对训练的效果产生了质疑。我还对搞学长说：『训练根本就没有什么用，该会的知识都已经会了，那都是智商题，临场想得出来就想得出来，想不出来就想不出来，就这样了。』后来一年练多了以后才明白那种忽好忽坏，其实就是菜。理解还不够深刻，手还不够熟练。当思维熟练到一定程度的时候，解法和灵感就自然来了。

所谓的创新，也不过是把相似的东西联系结合起来罢了。人的联想能力是有限的，所以当我们面对很难的问题的时候，如果你的记忆里储备的相关内容不够多，是不可能把他们联系结合起来的。除了要提升自己知识储备的量以外，对学习到的内容加深理解也是很重要的。所谓加深理解，就是提取事物的本质特征。因为最终你能联想到相关的东西，一定是因为一些共同的本质特征。如果你事先提取好这些特征放在脑子里(做法就是平常对遇到的事物多思考)，那么联想起来就容易很多了。人类的思考模式有点像广度优先搜索，遇到问题，先找最相关的一堆东西，不能解决再找次相关的一堆东西。这里简单想一下就会知道这个『相关事物的量』相对于从问题到要找的东西的距离是指数级的。所以你平常不思考做好索引，搜索起来肯定就慢得要死了…还很可能超出你能搜的能力极限，反映到实际就是，你搞不定这个问题了。

分析了这么多，就是要印证这个标题：努力一定会有提高的。能到什么程度不知道，但一定可以比原来强。

适当展示自己

这一项的目的不是为了show off，而是为了调节他人对自己的期望。有些牛人确实很低调，那是因为他们不再需要周围人改变对他的期望来实现自己的价值。我觉得之前在依图那边听来的一句话非常正确，大意是：一个人的成长是由他做的事情决定的。

如果你做的东西都是打杂，那成长的速度是很慢的。

而对于我们刚出来社会工作的new graduate来说，在大公司被boss拿去打杂是十有八九的。要去做重要的有难度的事情，就必须要秀你自己的能力。万事开头难，当你抓住机会表现了一两次以后，别人对你的期望就会得到改变。这时候拿到了一些有意思的活就不要再表现得那么强势了，不然最后不能meet老板的期望就适得其反了。

强者的谦虚才是真的谦虚。当在别人的期望里还是个弱者的时候，再谦虚就没人会注意了。记得大酒神打dota1 solo大赛的时候杀完对面的鸡打的那一句：对不起，这场比赛我要赢。人都是需要机会来证明自己的。当你被推到那个舞台之后，自然而然就会变强了。

不过呢，这一点在比较小的创业公司就没有这个问题，反正事情都干不完，you can you up…

就像@Lpuck跟我说的：你玩宠物小精灵的时候，一个怪也就是一开始厉害一点，后面你一直用，他升级飞快，就很厉害了。展示自己，做的就是让自己“看起来厉害一点”。

坚持自己的想法

别人的意见要看，但是不要随便就接纳。犹记得刚进来的时候，随便一个提交都好多comments。然后当时比较naive，觉得他们说得有一点道理的都照着改。结果一会儿你把这次的经验用到下一个提交上面的时候，又有一个另外的人来说，你这里不应该这样…然后我就意识到其实这群比我senior的人之间其实都不能统一意见。在那之后，如果不是我想过非常有道理的意见，基本都坚持自己的想法。

每个人都有不同的想法，所以外界的意见是不可能保持自洽的，能自洽的只有你自己的体系。但是当外界对某件事形成一个统一的想法的时候，就要特别注意思考其原因。虽然这种意见不一定对，但即使是错的，也值得积累下来的。这样在你带领别人的那一天，就能快速理解别人的动机并指正。

看《Effective Java》看到的，主要讲对Java equals的override。C++对==的重载也是一样的。下文就用Java举例子了，因为是OOP的通用问题，所以很容易类比到C++。

问题描述：

class A {
    int x;

    public A(int x) {
        this.x = x;
    }

    @Override
    boolean equals(Object o) {
        if (o instanceof A) {
            return x == (A)(o).x;
        } else {
            return false;
        }
    }
}

class B extends A {
    int y;

    public B(int x, int y) {
        super(x);
        this.y = y;
    }
}

以上代码中B如果想Override equals使得y也能加入判断，应该怎么做？

也许最直接的答案是

    @Override
    boolean equals(Object o) {
        if (o instanceof B) {
            return x == (B)(o).x && y == (B)(o).y;
        } else {
            return false;
        }
    }

然而equals需要的是一种等价关系，需要满足三个条件：

自反性。即x.equals(x)为真。
对称性。即x.equals(y) == y.equals(x)
传递性。即x.equals(y) && y.equals(z)，则x.equals(z)

上面这个做法明显对称性会崩盘。
A a = new A(0);
A b = new B(0, 0);
a.equals(b); //true
b.equals(a); //false

那如果加入对父类的特判呢？对称性是没问题的，但是传递性会崩。
A a = new B(0, 0);
A b = new A(0);
A c = new B(0, 1);
a.equals(b); //true
b.equals(c); //true
a.equals(c); //false

实际结论是B根本没有办法重载一个合理的equals。

证明：因为不能更改A类的equals，因此A的实例equals B的实例的时候一定会只判x然后返回true。那么根据对称性，B类的实例equals对应A类的实例的时候，也一定要返回true。所以如果想要在B的equals中判断y，上面传递性的问题一定会出现。至此对称性和传递性不可能同时满足，所以不可能存在科学的重载方法。
这个从本质来讲，父类和子类的相等是一种偏序关系，然而equals要的是等价关系，所以被父类强行equals为true以后，就怎么也救不回来了。
那么我们放松一下条件，允许修改父类呢？

从上面的教训可以知道如果子类和父类之间可以相等的话，一定会GG。那只能做成不相等了。

于是直接getClass判吧，直接看new的时候是什么的类，不同就直接判不等。那么假如A多了一个方法。
    private static final Set <a> luckyA = new HashSet<>()
    static {
        luckyA.add(new A(5));
        luckyA.add(new A(10));
    }

    public boolean isLucky(A a) {
        return luckyA.contains(a);
    }

这个isLucky写得再正常不过了，然而如果我们那么做，那这个isLucky对于所有子类就失效了。这违背了OOP的Liskov substitution principle。

Wiki上的定义：Subtype Requirement: Let  be a property provable about objects x of type T. Then  should be true for objects y of type S where S is a subtype of T.
你也许会想，不加这个isLucky不就没有违反了吗？是的，但是只要A中有依赖A的equals的方法，就会违反这个规则。
然而你觉得因为子类的一个equals问题，给父类定下不能依赖自己的equals实现任何功能的规矩，合理吗？
综上所述，父类与子类equals可以为true是不行的；然而一律为false又会break OOP的原则。于是我们可以推导出即使允许同时修改父类和子类的equals，也没有任何合理的写法。这也是《Effective Java》给出的结论。
形式化描述一下这个结论：
如果父类是可实例化的(非abstract，非interface)，子类如果添加了新的域想override equals把这个域放进去，没有任何一种override的方法是合理的。
那么该怎么做呢？答案：不要用继承，用组合。然后加一个fallback的方法。
class B {
    A a;
    int y;

    public asA() {
        return a;
    }
}

	

从今年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