終于交上了這一周的作業(yè)。
一者是因為我市賽發(fā)揮巨爛回頭做了一些水題，二者是為了初中市賽忙前忙后浪費了不少時間。
能交上這一周的作業(yè)還是很高興的。

LCA-倍增法（這個被淘汰了）
±1RMQ     （還沒有學習）

memory ：RMQ-ST （AC）
              笛卡爾樹+LCA-Tarjan (AC)    弱弱的數(shù)據(jù)都比ST快一倍呢 

ancestor: LCA-Tarjan (AC)

                歐拉序列+RMQ （AC）這個一點都不快啊，還要學習±1RMQ

ADD:sur（2011市賽DAY1第二題，當時無人AC，最牛的選手爆內(nèi)存了。。。）
        一道簡單搜索，但對隊列大小，hash方法要求較高。
         不小心被我用 手寫的萬能QUEUE + STL_SET   AC了。。。。
同時研究的STL的優(yōu)先隊列和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;
        }
還有笛卡爾樹是一種會旋轉(zhuǎn)的平衡樹，類似于treap，常用來解決treap的退鏈問題。
由于我不會treap,也不打算學treap,所以重頭研究了一下子，網(wǎng)上盜版極多（全是nlogn,那要它干什么）
最后找到一種比較簡單的構(gòu)樹方法，類似于SBT和SPLAY的操作放增設(shè)虛擬根節(jié)點。
核心代碼：
Data[1]=INF;//虛擬根節(jié)點
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;
        }