终于交上了这一周的作业。
一者是因为我市赛发挥巨烂回头做了一些水题，二者是为了初中市赛忙前忙后浪费了不少时间。
能交上这一周的作业还是很高兴的。
LCA-倍增法（这个被淘汰了）
±1RMQ （还没有学习）
memory ：RMQ-ST （AC）
笛卡尔树+LCA-Tarjan (AC) 弱弱的数据都比ST快一倍呢
ancestor: LCA-Tarjan (AC)
欧拉序列+RMQ （AC）这个一点都不快啊，还要学习±1RMQ
ADD:sur（2011市赛DAY1第二题，当时无人AC，最牛的选手爆内存了。。。）
一道简单搜索，但对队列大小，hash方法要求较高。
不小心被我用 手写的万能QUEUE + STL_SET AC了。。。。
同时研究的STL的优先队列和map。
只剩下±1RMQ了。
说明：由于受到某讲义的错误指导，我一直都不会写Tarjan算法。
其实核心代码巨简单：
int Getpar(int a){if(par[a]!=a)par[a]=Getpar(par[a]);return par[a];}//并查集
void Tarjan(int i){//Q询问链表，E边链表
vis[i]=true;par[i]=i;
for(int p=Qhead[i];p;p=Qnext[p])
if(vis[Qto[p]])ans[Getpar(Qto[p])]++;
for(int p=Ehead[i];p;p=Enext[p])
if(!vis[Eto[p]])Tarjan(Eto[p]),par[Eto[p]]=i;
}
还有笛卡尔树是一种会旋转的平衡树，类似于treap，常用来解决treap的退链问题。
由于我不会treap,也不打算学treap,所以重头研究了一下子，网上盗版极多（全是nlogn,那要它干什么）
最后找到一种比较简单的构树方法，类似于SBT和SPLAY的操作放增设虚拟根节点。
核心代码：
Data[1]=INF;//虚拟根节点
FOR(i,2,n+1)Insert(i);
void Insert(int i){
int j=i-1;for(;Data[j]<=Data[i]&&Father[j];j=Father[j]);
Left[i]=Right[j],Father[Right[j]]=i,Right[j]=i,Father[i]=j;
}