終于交上了這一周的作業(yè)。
一者是因?yàn)槲沂匈惏l(fā)揮巨爛回頭做了一些水題，二者是為了初中市賽忙前忙后浪費(fèi)了不少時(shí)間。
能交上這一周的作業(yè)還是很高興的。
LCA-倍增法（這個(gè)被淘汰了）
±1RMQ （還沒有學(xué)習(xí)）
memory ：RMQ-ST （AC）
笛卡爾樹+LCA-Tarjan (AC) 弱弱的數(shù)據(jù)都比ST快一倍呢
ancestor: LCA-Tarjan (AC)
歐拉序列+RMQ （AC）這個(gè)一點(diǎn)都不快啊，還要學(xué)習(xí)±1RMQ
ADD:sur（2011市賽DAY1第二題，當(dāng)時(shí)無人AC，最牛的選手爆內(nèi)存了。。。）
一道簡(jiǎn)單搜索，但對(duì)隊(duì)列大小，hash方法要求較高。
不小心被我用 手寫的萬能QUEUE + STL_SET AC了。。。。
同時(shí)研究的STL的優(yōu)先隊(duì)列和map。
只剩下±1RMQ了。
說明：由于受到某講義的錯(cuò)誤指導(dǎo)，我一直都不會(huì)寫Tarjan算法。
其實(shí)核心代碼巨簡(jiǎn)單：
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;
}
還有笛卡爾樹是一種會(huì)旋轉(zhuǎn)的平衡樹，類似于treap，常用來解決treap的退鏈問題。
由于我不會(huì)treap,也不打算學(xué)treap,所以重頭研究了一下子，網(wǎng)上盜版極多（全是nlogn,那要它干什么）
最后找到一種比較簡(jiǎn)單的構(gòu)樹方法，類似于SBT和SPLAY的操作放增設(shè)虛擬根節(jié)點(diǎn)。
核心代碼：
Data[1]=INF;//虛擬根節(jié)點(diǎn)
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;
}