在C++遭遇的vector灵异事件

完整代码就不po了,核心代码大概是这样的

#include <iostream>
#include <vector>
std::vector<int> pool;
int alloc(){
	pool.push_back(0);
	return pool.size()-1;
}
int main(){
	pool.push_back(0);
	pool[0]=alloc();
	std::cout<<pool[0]<<std::endl;
}

pool里面已经有了一个元素,再由alloc往里面插入一个,size应该是2,返回值应该是1,pool[0]应该是1才对。然而输出是0。

坑爹的调了半天bug以后发现alloc以后vector被重新分配了,然而寻址寻到的还是原先的pool[0],所以甚至时不时会有Segmentation Fault的情况。

大概就是这样表情

羊踹玉兔,玉兔喊疼。

Vim的IJKL键位

今天偶然得知Vim方向键的正确食用方式是只用右手

然后瞬间觉得好不习惯啊表情

于是由WASD联想到用IJKL

用了用似乎还不错的啦(H键代替I成为了插入)

noremap i k
noremap j h
noremap h i
noremap k j

Linux目录的Execute权限

把文件系统看成一棵树。把目录想象成树里面的一个节点,文件是叶子节点。

struct node{
    list<pair<string/*name*/,node*> > son;
    int32 permission;
    int owner,group;
    time modified,created,accessed.
};

Write:可以编辑,也就是可以写、删除son列表。

Read:可以读取son列表的string部分(但是没有node*部分所以无法实际找到文件的位置)。

Execute:可以向这个node查询给定的name对应的node*的实际位置,因此可以访问到子文件。

关于申请美帝学校本科,从中介那get的一些姿势

  1. SAT胜过一切,Hurrah(个屁,你2100也好意思拿出来讲)
  2. 本科的Major排名并没有什么卵用,因为排名机构根本没有依据。想想很有道理,研究生排名可以根据Graduate House发表的论文数,或者(曾)学生获的奖项,或者研究出的神奇项目来排名。但是本科就没什么依据了,所以本科排名大多数是参考研究生排名的。(当然一个值得注意的副作用是不明真相的国际学生会依据本科排名去申请学校,无形中加剧了竞争)像我,看Purdue的CS本科排名相当靠前想申来做保底,然而它的综合排名太后中介说非常没有必要捂脸熊流泪我这种分数真的能随随便便UIUC或者Michigan Ann Arbor这种学校吗
  3. 此条不申UC可以无视。UC的各个分校申请用的同一个系统,所以如果中介是按申请数目收钱的话UCLA和Berkeley申一所就够了。第一是两校要求差不多,所以一所被拒另一所希望也不会大;第二是中介只需要申请的时候多打一个勾,所以作为甲方挺亏的。。。(我当然申了神校Berkeley)
  4. (其实是3.5)据说UCLA是全美申请人数最多的学校,因为LA生活舒服,UCLA校风开放,加州阳光温暖。(好湿!好湿啊!啪啪啪啪啪啪)
  5. 申高端学校适而可止。我原本高端想申请MIT、Princeton、Caltech、Cornell、Stanford,被顾问打回说这样相当冒险。最后留了MIT、Princeton和Cornell,一是Caltech在加州物价较高,二是斯坦福我希望较渺茫加上本来并不是很有感;MIT和Princeton是梦想学校啦,不申后悔;Cornell的性价比(期望收益)较高(录取率10%+).话说为什么把Berkeley划分到一等学校那一档呢(Ivies、MIT、Stanford和Caltech之流算超一流),按录取率确实高很多,但是也是Cornell水平啊,入个体育联盟很了不起吗Cornell?(嫌弃脸)
  6. 口音对于面试而言很重要,而面试对于申请而言很重要,而申请对于录取而言很重要。总结:口音很重要。(TOEFL Speaking 20掩面逃)

先那么多,有什么新东西再补

树套树笔记

没错这是个大坑

这两天看到一鬼畜题,带插入区间k小值,BZOJ3065,网上搜的hzwer写法貌似是替罪羊树套线段树(?!!)省队里面一神犇也大致给我讲了讲,说实话,并没有怎么听懂Orz

总之先从最基础的树套树开始,也就是带修改区间k小值

静态的区间k小值大家都会做,内存换时间就划分树,时间换内存就主席树

带修改区间k小值呢,其实思路和主席树差不多(主席树:要是我能查询[a,b)区间里进入左子树的数的个数就好了!),要是我能查询[a,b)区间里进入左子树的数的个数就好了。但是带修改怎么查呢?

假设对于一个区间,有数组flag_inleft,其中flag_inleft[i]==1表示元素i进入左子树,==0表示进入右子树,那么对于区间[a,b),我们只要求sum {i | a<=i<b }的值就能达到目的了。

好了,那么我们在每个区间里面放一颗树状数组或者线段树…就能logn的时间查询上诉sansum值了,每次查询时间(应该是不紧却的)上界是O(log^2(n)),(因为树高logn,每个节点查询又需要logn(感觉这里不紧却))。还是很好写的。

(我会回来填坑的)

(我回来填坑了)

其实这题用Splay也可以写的嘛,主席树套Splay。

众所周知Splay是可以维护区间的,鉴于查询区间k大的时候我们只需要主席树的每一个节点支持查询“到i的时候有多少个数进入了左边”,而Splay又支持快速的插入和查询前缀和…后面就不用详细展开了。

更加抽象一点,对于序列上的一个区间k小类型的操作f,执行这个操作的复杂度为O(f*logn)。因为在主席树上一共要经过logn那么多个点,而每个点都要花O(f)维护。

例如主席树,查询(二分)是logn的,所以主席树整体查询复杂度是O(logn*logn)。

例如划分树,查询(二分)是1的,所以划分树整体查询复杂度是O(1*logn)。

例如带修改的主席树(主席树套树状数组),修改操作(在树状数组上)是logn的,所以整体修改复杂度是O(logn*logn)