您的位置：首頁 > 軟件教程 > 教程 > 平衡樹 Treap & Splay [學(xué)習(xí)筆記]

平衡樹 Treap & Splay [學(xué)習(xí)筆記]

來源：好特整理　|　時(shí)間：2024-05-25 09:45:58 |　閱讀：190　|　 標(biāo)簽： T Play S 平衡 EA 　 |　分享到：

平衡樹 \(\tt{Treap}\) & \(\tt{Splay}\) 壹.單旋 \(\tt{Treap}\) 首先了解 \(\tt{BST}\) 非常好用的東西，但是數(shù)據(jù)可以把它卡成一條鏈 \(\dots\) 于是，我們將 \(\tt{Tree}\) 與 \(\tt{heap}\) (堆)

平衡樹 \(\tt{Treap}\) & \(\tt{Splay}\)

壹.單旋 \(\tt{Treap}\)

首先了解 \(\tt{BST}\)

非常好用的東西，但是數(shù)據(jù)可以把它卡成一條鏈 \(\dots\)

于是，我們將 \(\tt{Tree}\) 與 \(\tt{heap}\) (堆) 合并，以保證平衡樹 \(\log\) 的深度。

具體地，我們可以使用旋轉(zhuǎn)操作實(shí)現(xiàn)

平衡樹 Treap & Splay [學(xué)習(xí)筆記]

K8He的圖

以右旋為例，我們發(fā)現(xiàn)，本來的中序遍歷順序?yàn)? \(y ，那么對于 \(q\) 右旋，即將左兒子旋上來，由于本來 \(p ，所以顯然 \(q\) 要成為 \(p\) 的右兒子。那就剩下 \(x\) 無家可歸，我們發(fā)現(xiàn) \(p ，那么 \(q\) 的左兒子再適合不過了。

我們規(guī)定 \(0\) 方向?yàn)樽螅? \(1\) 方向?yàn)橛�，即可通過 \(d\) ^ \(1\) 實(shí)現(xiàn)方向取反。

一般的，對于一個(gè)節(jié)點(diǎn) \(i\) ，如果將其 \(d\) 方向上的兒子 \(s\) 旋上去，那么 \(i\) 要成為 \(s\) 在 \(d\) ^ \(1\) 方向上的兒子， \(s\) 原來在 \(d\) ^ \(1\) 方向上的兒子要成為 \(i\) 在 \(d\) 方向上的兒子。 

void rotate(int &i,int d){
    int s=t[i].son[d];
    t[i].son[d]=t[s].son[d^1];
    t[s].son[d^1]=i;
    up(i),i=s,up(i);
    return;
}

那么我們什么時(shí)候進(jìn)行旋轉(zhuǎn)呢？還記得我們說過要利用堆的性質(zhì)，那么我們對每個(gè)節(jié)點(diǎn)隨機(jī)一個(gè)優(yōu)先級，將它按照小根堆或大根堆存，若當(dāng)前不滿足堆的性質(zhì)了，那就旋轉(zhuǎn)。

  • 插入操作，從根往下跑，但要注意不滿足堆的性質(zhì)時(shí)，考慮旋轉(zhuǎn)。 
void insert(int &i,int k){
    if(!i){
        i=++tot;
        t[i].cnt=t[i].siz=1;
        t[i].val=k,t[i].rd=rnd();
        return;
    }
    t[i].siz++;
    if(t[i].val==k){
        ++t[i].cnt;return;
    }
    int d=(t[i].valt[t[i].son[d]].rd)  rotate(i,d);
    return;
}
  • 刪除操作，先找節(jié)點(diǎn)，如果只有一個(gè)兒子，讓兒子替換它，否則讓兒子旋上來(當(dāng)然要滿足堆性質(zhì))，然后一直旋，直到剩一個(gè)兒子或者成為葉子節(jié)點(diǎn)。 
void del(int &i,int k){
    if(!i)  return;
    if(t[i].val==k){
        if(t[i].cnt>1){
            --t[i].cnt,--t[i].siz;
            return;
        }
        int d=(t[ls(i)].rd>t[rs(i)].rd);
        if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
        else  rotate(i,d),del(i,k);
        return;
    }
    t[i].siz--;
    int d=t[i].val
  • 查排名，看代碼理解即可。 
int rk(int i,int k){
    if(!i) return 1;
    if(t[i].val>k)  return rk(ls(i),k);
    if(t[i].val
  • 查第 \(k\) 大，思想和線段樹一樣。 
int kth(int i,int k){
    while(1){
        if(k<=t[ls(i)].siz)  i=ls(i);
        else if(k>t[ls(i)].siz+t[i].cnt)
            k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
        else return t[i].val;
    }
}
  • 前驅(qū)后繼，和普通 \(\tt{BST}\) 一樣。 
int pre(int i,int k){
    if(!i)  return -1e8;
    if(t[i].val>=k)  return pre(ls(i),k);
    return max(pre(rs(i),k),t[i].val);
}
int nex(int i,int k){
    if(!i)  return 1e8;
    if(t[i].val<=k)  return nex(rs(i),k);
    return min(nex(ls(i),k),t[i].val);
}

對于單旋 \(\tt{Treap}\) ，我們只需要理解旋轉(zhuǎn)操作即可，畢竟下面的 \(\tt{Splay}\) 還要用它，請務(wù)必看懂旋轉(zhuǎn)操作，其他的， 還是FHQ好打， 差不多看看就行，應(yīng)用范圍不大。

(板子封裝在下面題單 普通平衡樹 里)

貳.無旋 \(\tt{FHQ\ Treap}\)

由于單旋 \(\tt{Treap}\) 不好打且擴(kuò)展功能不多，所以我們引入新的 \(\tt{FHQ\_ Treap}\) ，好像是神范浩強(qiáng)發(fā)明的，%%%%%%。

網(wǎng)上都說FHQ比單旋好理解，我表示理解了之后確實(shí)好理解，但你得先理解(我看了一個(gè)多小時(shí)才看懂，不過我是fw)

好那么直入正題 —— \(\tt{FHQ\_ Treap}\)

既然也是 \(\tt{Treap}\) ，那就是一樣的，也是靠堆性質(zhì)，它的不同之處就在于，它無旋，它是靠 分裂+合并 來保證 \(\log\) 的深度。

具體地，分裂方式有兩種，一種是按權(quán)值分裂，另一種是按照子樹大小分裂:

  • 按照權(quán)值分裂，比如將以 \(i\) 為根的平衡樹分成兩棵平衡樹，根分別是 \(x,y\) ，要求樹 \(x\) 的權(quán)值都小于等于 \(k\) ,剩下是 \(y\) ，那么分討:
    • 如果 \(val(i)<=k\) ，那么 \(i\) 的整棵左子樹一定都小于 \(k\) ，肯定都要?jiǎng)澋? \(x\) 里，則令 \(x=i\) ，繼續(xù)遞歸劃分 \(rs(i)\) 即可。
    • 否則， \(i\) 的整棵右子樹一定都大于 \(k\) ，肯定都要?jiǎng)澋? \(y\) 里，則令 \(y=i\) ，繼續(xù)遞歸劃分 \(ls(i)\) 即可。

注意取地址。 

void split(int i,int k,int &x,int &y){
    if(!i){x=y=0;return;}
    if(val(i)>k)   y=i,split(ls(i),k,x,ls(i));
    if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
    up(i);return;
}
  • 按照子樹大小分裂，還是將以 \(i\) 為根的平衡樹分成兩棵平衡樹，根分別是 \(x,y\) ，要求是 \(siz(x)=k\) ，還是和上面一樣:
    • 如果 \(siz(ls(i))+cnt(i)<=k\) ，那么 \(i\) 的整棵左子樹和 \(i\) 肯定都要?jiǎng)澋? \(x\) 里，則令 \(x=i\) ，繼續(xù)遞歸劃分 \(rs(i)\) 即可。
    • 否則， \(i\) 的整棵右子樹肯定都要?jiǎng)澋? \(y\) 里，則令 \(y=i\) ，繼續(xù)遞歸劃分 \(ls(i)\) 即可。

按子樹大小分裂，一般用在平衡樹維護(hù)序列，后面的 \(\tt{Splay}\) 也是一樣。 

void split(int i,int k,int &x,int &y){
    if(!i){x=y=0;return;}
    if(siz(ls(i))+cnt(i)<=k)  x=i,split(rs(i),k-(siz(ls(i))+cnt(i)),rs(i),y);
    else  y=i,split(ls(i),k,x,ls(i));
    up(i);
}
  • 下一個(gè)操作是合并， \(\tt{FHQ\_ Treap}\) 正是通過它保證的堆性質(zhì)，設(shè)要合并的兩棵樹的根分別為 \(x,y\) ，設(shè)堆性質(zhì)為大根堆。
    • 若 \(rd(x)>rd(y)\) 則把 \(x\) 定為根，然后繼續(xù)遞歸合并 \(rs(x)\) 和 \(y\)
    • 否則把 \(y\) 定為根，然后繼續(xù)遞歸合并 \(x\) 和 \(ls(y)\) 
void merge(int &i,int x,int y){
    if(!x||!y){i=x|y;return;}
    if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
    else  merge(ls(y),x,ls(y)),i=y;
    up(i);return;
}
  • 插入 \(k\) ，先分裂出 \(<=k-1\) ，合并時(shí)把 \(k\) 合并進(jìn)去。 
void insert(int k){
    int rt1,rt2;
    split(rt,k-1,rt1,rt2);
    merge(rt,rt1,New(k));merge(rt,rt,rt2);
    return;
}
  • 刪除 \(k\) ，把 \(k\) 分裂出來，然后把 \(k\) 用它的左右子樹合并替代，再合并。 
void del(int k){
    int rt1,rt2,cut;
    split(rt,k-1,rt1,rt2);split(rt2,k,cut,rt2);
    merge(cut,ls(cut),rs(cut));
    merge(rt,rt1,cut);merge(rt,rt,rt2);
    return;
}
  • 查排名，分裂完 \(\leq k-1\) 的樹大小 \(+1\) 
int rk(int i,int k){
    int rt1,rt2,res;
    split(i,k-1,rt1,rt2);
    res=siz(rt1)+1;
    merge(i,rt1,rt2);
    return res;
}

  • 第 \(k\) 小，和普通 \(\tt{Treap}\) 一樣。

  • 前驅(qū)后繼，以前驅(qū)為例，分裂出 \(\leq k-1\) ，那么這部分都小于 \(k\) ，找出最大值即可，一直跑右兒子，后繼同理。 

int pre(int &i,int k){
    int rt1,rt2,res;
    split(i,k-1,rt1,rt2),res=rt1;
    while(rs(res))  res=rs(res);
    merge(i,rt1,rt2);
    return val(res);
}
int nxt(int &i,int k){
    int rt1,rt2,res;
    split(i,k,rt1,rt2),res=rt2;
    while(ls(res))  res=ls(res);
    merge(i,rt1,rt2);
    return val(res);
}

(板子封裝在下面題單 普通平衡樹 里)

叁.雙旋 \(\tt{Splay}\)

\(\tt{Splay}\) 不同于以上兩種 \(\tt{Treap}\) ，它不再依靠隨機(jī)的優(yōu)先級保證深度，而是通過不斷旋轉(zhuǎn)來達(dá)到目的。

類似于單旋，只不過單旋是將某節(jié)點(diǎn)的兒子旋上來，而 \(\tt{Splay}\) 是將某節(jié)點(diǎn)自身旋上去，單次旋轉(zhuǎn)和 \(\tt{Treap}\) 一樣，但是要多記錄一個(gè)父親

具體地，旋轉(zhuǎn) \(x\) 時(shí)，令 \(y\) 為 \(x\) 的父親， \(z\) 為祖父，設(shè) \(x\) 為 \(y\) 在 \(d\) 方向上的兒子，則單次旋轉(zhuǎn)可分為這幾步:

  • \(x\) 替換 \(y\) 成為 \(z\) 的兒子
  • \(x\) 在 \(d\) ^ \(1\) 方向的兒子下放給 \(y\) 當(dāng) \(d\) 方向的兒子
  • \(y\) 充當(dāng) \(x\) 在 \(d\) ^ \(1\) 方向的兒子

三次修改，三次認(rèn)爹， rotate 就寫完了 

#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1] 
void rotate(int x){
    int y=fa(x),z=fa(y);
    int d=(rs(y)==x);
    t[z].son[(rs(z)==y)]=x;fa(x)=z;
    ds(y)=bs(x);fa(bs(x))=y;
    bs(x)=y;fa(y)=x;
    up(y),up(x);
}

然后便是 \(\tt{Splay}\) 的核心操作， splay 如說

具體地， splay 操作是將節(jié)點(diǎn) \(x\) 旋轉(zhuǎn)到目標(biāo)節(jié)點(diǎn) \(s\) 的兒子，若 \(s=0\) 則為旋轉(zhuǎn)到根。那么如果我們一直一直單旋上去的話我們會(huì)發(fā)現(xiàn)一個(gè)嚴(yán)重的問題——雖然 \(x\) 上去了，但是它的最大深度依然沒變，也就是說，轉(zhuǎn)了個(gè)寂寞。。

那么怎么辦，進(jìn)行雙旋，討論幾種情況——( \(x,y,z\) 意義同上)

  • \(z=s\) 直接將 \(x\) 單旋一次上去

  • \(z\not ={s}\)

    • \(x,y,z\) 三點(diǎn)共線，即

    平衡樹 Treap & Splay [學(xué)習(xí)筆記]

    此時(shí)我們應(yīng)先轉(zhuǎn) \(y\) 再轉(zhuǎn) \(x\)

    平衡樹 Treap & Splay [學(xué)習(xí)筆記] - 平衡樹 Treap & Splay [學(xué)習(xí)筆記]

    • \(x,y,z\) 三點(diǎn)不共線，直接旋轉(zhuǎn)兩次 \(x\)

    平衡樹 Treap & Splay [學(xué)習(xí)筆記] - 平衡樹 Treap & Splay [學(xué)習(xí)筆記]

就這樣旋旋旋，就能保證深度OK，每次插入節(jié)點(diǎn)后都要進(jìn)行一次 Splay 

void splay(int x,int s){
    while(fa(x)!=s){
        int y=fa(x),z=fa(y);
        if(z!=s)
            (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(!s)  rt=x;
}

至于這么旋為什么可以讓復(fù)雜度OK，使用什么 "勢能分析法" ，我是fw我不會(huì)。

\(\tt{Splay}\) 與 \(\tt{FHQ}\) 一樣，也是兩種維護(hù)方式，一種維護(hù)權(quán)值，一種維護(hù)下標(biāo)(即序列的中序遍歷)。

然后就是 \(\tt{Splay}\) 的一些基本操作:

  • 插入，有兩種方式，即按權(quán)值和子樹大小，與 \(\tt{FHQ}\) 類似，注意要記錄一下父親節(jié)點(diǎn)

    • 按照權(quán)值插入 
    void insert(int k){
    int p=rt,f=0;
    while(p&&val(p)!=k){
        f=p;
        p=t[p].son[val(p)
    • 按照子樹大小插入，可以遞歸寫(愛咋寫咋寫) 
    void insert(int &i,int f,int x,int k){
    if(!i){
        i=++tot;
        siz(i)=1;fa(i)=f;val(i)=k;
        return;
    }
    if(x<=siz(ls(i))+1)  insert(ls(i),i,x,k);
    else  insert(rs(i),i,x-siz(ls(i))-1,k);
    up(i);
}

  • 對于 splay ，我們要先找到某權(quán)值對應(yīng)的節(jié)點(diǎn)，直接找然后 splay

    • 權(quán)值 
    void find(int k){
    if(!rt)  return;
    int p=rt;
    while(t[p].son[val(p)
    • 子樹大小 
    void find(int x){
    if(!rt)  return;
    int p=rt;
    while(siz(ls(p))+1!=x){
        if(x<=siz(ls(p))+1){
            p=ls(p);
        }
        else{
            x-=(siz(ls(p))+1);
            p=rs(p);
        }
    }
    splay(p,0);
}

  • 查第 \(k\) 小，與 \(\tt{Treap}\) 同理，不再贅述

  • 查排名，轉(zhuǎn)到根節(jié)點(diǎn)后左子樹的大小 \(+1\) 即可

  • 查前驅(qū)后繼，以前驅(qū)為例，轉(zhuǎn)到根之后左子樹里最大值即前驅(qū)，后繼同理

  • 刪除比較有意思，我們先找到前驅(qū)后繼，然后將前驅(qū) splay 到根，將后繼 splay 到前驅(qū)的右兒子，那么要?jiǎng)h除的節(jié)點(diǎn)就一定為 \(ls(rs(rt))\) (如下圖)。這也就意味著必須有前驅(qū)后繼，否則刪不了，那么直接插入兩個(gè)極值哨兵節(jié)點(diǎn)即可。 

     pre
    /   \
  ...   nxt
        /  \
      cut  ...

void del(int k){
    int prek=pre(k);
    int nxtk=nxt(k);
    splay(prek,0);splay(nxtk,prek);
    int cut=ls(nxtk);
    if(cnt(cut)>1)
        --cnt(cut),splay(cut,0);
    else  ls(nxtk)=0;
}

另外，維護(hù)序列的 \(\tt{Splay}\) 進(jìn)行區(qū)間操作時(shí)，也是將區(qū)間轉(zhuǎn)化為子樹,和刪除操作類似，比如 文藝平衡樹 就是這樣，不再贅述。

最后注意一定要插哨兵

(板子封裝在下面題單 普通平衡樹 里)

肆. \(hs\) 題單

\(T_D\) 普通平衡樹

由于是純板子，所以先掛 \(T_D\) 。

普通Treap 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 100010
int m;

namespace TREAP{
    mt19937 rnd(0x7f);
    struct Treap{
        int son[2],cnt,siz,val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
    }t[N];
    int tot,rt;
    void up(int i){
        t[i].siz=t[ls(i)].siz+t[rs(i)].siz+t[i].cnt;
    }
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        up(i),i=s,up(i);
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            t[i].cnt=t[i].siz=1;
            t[i].val=k,t[i].rd=rnd();
            return;
        }
        t[i].siz++;
        if(t[i].val==k){
            ++t[i].cnt;return;
        }
        int d=(t[i].valt[t[i].son[d]].rd)  rotate(i,d);
        return;
    }
    void del(int &i,int k){
        if(!i)  return;
        if(t[i].val==k){
            if(t[i].cnt>1){
                --t[i].cnt,--t[i].siz;
                return;
            }
            int d=(t[ls(i)].rd>t[rs(i)].rd);
            if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
            else  rotate(i,d),del(i,k);
            return;
        }
        t[i].siz--;
        int d=t[i].valk)  return rk(ls(i),k);
        if(t[i].valt[ls(i)].siz+t[i].cnt)
                k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
            else return t[i].val;
        }
    }
    int pre(int i,int k){
        if(!i)  return -1e8;
        if(t[i].val>=k)  return pre(ls(i),k);
        return max(pre(rs(i),k),t[i].val);
    }
    int nex(int i,int k){
        if(!i)  return 1e8;
        if(t[i].val<=k)  return nex(rs(i),k);
        return min(nex(ls(i),k),t[i].val);
    }
} using namespace TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    m=read;
    int op,x;
    while(m-->0){
        op=read,x=read;
        switch(op){
            case 1:
                insert(rt,x);break;
            case 2:
                del(rt,x);break;
            case 3:
                write(rk(rt,x));pt;break;
            case 4:
                write(kth(rt,x));pt;break;
            case 5:
                write(pre(rt,x));pt;break;
            case 6:
                write(nex(rt,x));pt;break;
        }
    }

    return 0;
}
FHQ_Treap 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=1e5+10;
namespace FHQ_TREAP{
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=cnt(i)+siz(ls(i))+siz(rs(i));
    }
    int New(int k){
        val(++tot)=k;
        cnt(tot)=siz(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)>k)   y=i,split(ls(i),k,x,ls(i));
        if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
        up(i);return;
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);return;
    }
    void insert(int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));merge(rt,rt,rt2);
        return;
    }
    void del(int k){
        int rt1,rt2,cut;
        split(rt,k-1,rt1,rt2);split(rt2,k,cut,rt2);
        merge(cut,ls(cut),rs(cut));
        merge(rt,rt1,cut);merge(rt,rt,rt2);
        return;
    }
    int rk(int i,int k){
        int rt1,rt2,res;
        split(i,k-1,rt1,rt2);
        res=siz(rt1)+1;
        merge(i,rt1,rt2);
        return res;
    }
    int kth(int i,int k){
        while(1){
            if(k<=siz(ls(i)))  i=ls(i);
            else if(k>siz(ls(i))+cnt(i))
                k-=(siz(ls(i))+cnt(i)),i=rs(i);
            else return val(i);
        }
    }
    int pre(int &i,int k){
        int rt1,rt2,res;
        split(i,k-1,rt1,rt2),res=rt1;
        while(rs(res))  res=rs(res);
        merge(i,rt1,rt2);
        return val(res);
    }
    int nxt(int &i,int k){
        int rt1,rt2,res;
        split(i,k,rt1,rt2),res=rt2;
        while(ls(res))  res=ls(res);
        merge(i,rt1,rt2);
        return val(res);
    }
} using namespace FHQ_TREAP;
int m;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    srand(time(0));
    m=read;
    int op,x;
    while(m-->0){
        op=read,x=read;
        switch(op){
            case 1:
                insert(x);
                break;
            case 2:
                del(x);
                break;
            case 3:
                write(rk(rt,x));pt;
                break;
            case 4:
                write(kth(rt,x));pt;
                break;
            case 5:
                write(pre(rt,x));pt;
                break;
            case 6:
                write(nxt(rt,x));pt;
                break;
            default:break;
        }
    }
    return 0;
}
Splay 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void find(int k){
        if(!rt)  return;
        int p=rt;
        while(t[p].son[val(p)k)  return p;
        p=rs(p);while(ls(p))  p=ls(p);
        return p;
    }
    void del(int k){
        int prek=pre(k);
        int nxtk=nxt(k);
        splay(prek,0);splay(nxtk,prek);
        int cut=ls(nxtk);
        if(cnt(cut)>1)
            --cnt(cut),splay(cut,0);
        else  ls(nxtk)=0;
    }
    int kth(int k){
        int i=rt;
        if(siz(i)siz(ls(i))+cnt(i))
                k-=(siz(ls(i))+cnt(i)),i=rs(i);
            else  return val(i);
        }
    }
} using namespace SPLAY;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    insert(-1e8);insert(1e8);
    int op,x;
    for(int i=1;i<=n;i++){
        op=read,x=read;
        switch(op){
        case 1:
            insert(x);break;
        case 2:
            del(x);break;
        case 3:
            find(x);
            write(siz(ls(rt))),pt;break;
        case 4:
            write(kth(x+1)),pt;break;
        case 5:
            write(val(pre(x))),pt;break;
        case 6:
            write(val(nxt(x))),pt;break;
        default:
            break;
        }
    }

    return 0;
}

\(T_A\) 營業(yè)額統(tǒng)計(jì)

板子，求前驅(qū)后繼。

普通Treap 
#include
using namespace std;
#define inf 1e10
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=(1<<15)+10;
int n;
int a;
int ans;
namespace TREAP{
    mt19937 Rand(0x7f);
    int tot,rt;
    struct Treap{
        int son[2],val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define val(i) t[i].val
        #define rd(i) t[i].rd
    }t[N];
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        i=s;
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            val(i)=k;rd(i)=Rand();
            return;
        }
        if(val(i)==k){
            return;
        }
        int d=(val(i)rd(t[i].son[d]))  rotate(i,d);
    }
    int pre(int i,int k){
        if(!i)  return -inf;
        if(val(i)>k)  return pre(ls(i),k);
        return max(val(i),pre(rs(i),k));
    }
    int nxt(int i,int k){
        if(!i)  return inf;
        if(val(i)
FHQ_Treap 
#include
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = (1<<15)+10;

namespace FHQ_TREAP{
    mt19937 Rand(0x7f);
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=cnt(i)+siz(ls(i))+siz(rs(i));
    }
    int New(int k){
        val(++tot)=k;
        cnt(tot)=siz(tot)=1;
        rd(tot)=Rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)>k)  y=i,split(ls(i),k,x,ls(i));
        if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    int pre(int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        if(!siz(rt1))  return -1e8;
        int res=rt1;
        while(rs(res))  res=rs(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    int nxt(int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        if(!siz(rt2))  return 1e8;
        int res=rt2;
        while(ls(res))  res=ls(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
} using namespace FHQ_TREAP;
int n,a;
int ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    a=read;
    insert(a);
    ans=a;
    for(int i=2;i<=n;i++){
        a=read;
        int prea=pre(a);
        int nxta=nxt(a);
        ans+=min(a-prea,nxta-a);
        insert(a);
    }
    write(ans);
    return 0;
}
Splay 
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void find(int k){
        if(!rt)  return;
        int p=rt;
        while(t[p].son[val(p)=k)  return p;
        p=rs(p);while(ls(p))  p=ls(p);
        return p;
    }
} using namespace SPLAY;
int a,ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    insert(-1e8);insert(1e8);
    a=read;
    ans=a;
    insert(a);
    for(int i=2;i<=n;i++){
        a=read;
        int prea=val(pre(a)),nxta=val(nxt(a));
        ans+=min(a-prea,nxta-a);
        insert(a);
    }
    write(ans);

    return 0;
}

\(T_B\) 寵物收養(yǎng)所

發(fā)現(xiàn)某時(shí)刻的平衡樹里只會(huì)全是人或者全是狗，查前驅(qū)后繼即可，查完即刪。

普通Treap 
#include
using namespace std;
#define int long long
#define inf 1e10
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=8*1e4+10;
const int p=1e6;
int n;
namespace TREAP{
    mt19937 Rand(0x7f);
    struct Treap{
        int son[2],cnt,siz,val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
        #define rd(i) t[i].rd
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        up(i),i=s,up(i);
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            cnt(i)=siz(i)=1;
            val(i)=k;rd(i)=Rand();
            return;
        }
        siz(i)++;
        if(val(i)==k){
            cnt(i)++;return;
        }
        int d=(val(i)rd(t[i].son[d]))  rotate(i,d);
        return;
    }
    void del(int &i,int k){
        if(!i)  return;
        if(val(i)==k){
            if(cnt(i)>1){
                --cnt(i),--siz(i);
                return;
            }
            int d=(rd(ls(i))>rd(rs(i)));
            if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
            else  rotate(i,d),del(i,k);
            return;
        }
        int d=(val(i)k)  return pre(ls(i),k);
        return max(val(i),pre(rs(i),k));
    }
    int nxt(int i,int k){
        if(!i)  return inf;
        if(val(i)
Splay 
#include
using namespace std;
#define int long long
#define inf 1e10
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 8*1e4+10;
const int p = 1e6;
int n;

namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void insert(int k){
        int p=rt,f=0;
        while(p && val(p)!=k){
            f=p;
            p=t[p].son[val(p)k)  return p;
        p=rs(p);while(ls(p))  p=ls(p);
        return p;
    }
    void del(int k){
        int prek=pre(k,0),nxtk=nxt(k,0);
        splay(prek,0);splay(nxtk,prek);
        int cut=ls(nxtk);
        if(cnt(cut)>1)  --cnt(cut),splay(cut,0);
        else  ls(nxtk)=0;
    }
} 
using namespace SPLAY;
bool now;
int num[2];
int a,b;
int ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    insert(-inf);insert(inf);
    n=read;
    now=read;b=read;num[now]=1;
    insert(b);
    for(int i=2;i<=n;i++){
        a=read,b=read;
        if(!num[a^1]){
            ++num[a],now=a;
            insert(b);
            continue;
        }
        if(a==now){
            ++num[now];
            insert(b);
        }
        else{
            int preb=val(pre(b,1)),nxtb=val(nxt(b,1));
            int hwr=(b-preb<=nxtb-b?preb:nxtb);
            ans=(ans+abs(hwr-b))%p;
            del(hwr);
            --num[now];
        }
    }
    write(ans);
    return 0;
}

注意 \(Splay\) 求前驅(qū)后繼時(shí) 如果要取等注意特判 ，刪除時(shí)不可取等(取等就寄了)

\(T_C\) 郁悶的出納員

維護(hù)整體懶標(biāo)記，每次刪除低于 \(minn-add\) 線的。

  • 用普通 \(\tt{Treap}\) 直接暴力刪，不好打。
  • 用 \(\tt{FHQ\_ Treap}\) 分裂出低于 \(minn-add\) 的部分，直接不要即可。

服了， \(\tt{FHQ\_ Treap}\) 跑不過普通 \(\tt{Treap}\) 的暴力。。。

普通Treap 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e6;
int n,minn;
int add;
int ans,sum;
int num;
namespace TREAP{
    mt19937 rnd(0x7f);
    struct Treap{
        int son[2],cnt,siz,val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define val(i) t[i].val
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
    }t[N];
    int tot,rt;
    void up(int i){
        t[i].siz=t[ls(i)].siz+t[rs(i)].siz+t[i].cnt;
    }
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        up(i),i=s,up(i);
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            t[i].cnt=t[i].siz=1;
            t[i].val=k,t[i].rd=rnd();
            return;
        }
        t[i].siz++;
        if(t[i].val==k){
            ++t[i].cnt;return;
        }
        int d=(t[i].valt[t[i].son[d]].rd)  rotate(i,d);
        return;
    }
    void del(int &i,int k){
        if(!i)  return;
        if(t[i].val==k){
            if(t[i].cnt>1){
                --t[i].cnt,--t[i].siz;
                return;
            }
            int d=(t[ls(i)].rd>t[rs(i)].rd);
            if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
            else  rotate(i,d),del(i,k);
            return;
        }
        t[i].siz--;
        int d=(t[i].valk)  return rk(ls(i),k);
        if(t[i].valt[ls(i)].siz+t[i].cnt)
                k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
            else return t[i].val;
        }
    }
    void dfs(int x){
        if(ls(x))  dfs(ls(x));
        if(rs(x))  dfs(rs(x));
        if(minn-add>val(x)){
            int c=cnt(x);
            for(int i=1;i<=c;i++)
                del(rt,val(x));
        }
    }

} using namespace TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,minn=read;
    char op;
    int k;
    for(int i=1;i<=n;i++){
        cin>>op;k=read;
        switch (op){
            case 'I':
                if(k>=minn)  insert(rt,k-add),++num; 
                break;
            case 'A':
                add+=k;
                break;
            case 'S':
                add-=k;
                dfs(rt);
                break;
            case 'F':
                if(siz(rt)
FHQ_Treap 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n,minn,add;

namespace FHQ_TREAP{
    mt19937 Rand(0x7f);
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    int New(int k){
        val(++tot)=k;
        siz(tot)=cnt(tot)=1;
        rd(tot)=Rand();
        return tot;
    }
    void spilt(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)>k)  y=i,spilt(ls(i),k,x,ls(i));
        if(val(i)<=k) x=i,spilt(rs(i),k,rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int k){
        int rt1,rt2;
        spilt(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
        return;
    }
    void del(int k){
        int rt1,rt2;
        spilt(rt,k-1,rt1,rt2);
        rt=rt2;
    }
    int kth(int i,int k){
        while(1){
            if(k<=siz(ls(i)))  i=ls(i);
            else if(k>siz(ls(i))+cnt(i))
                k-=(siz(ls(i))+cnt(i)),i=rs(i);
            else return val(i);
        }
    }
} using namespace FHQ_TREAP;

int sum,ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,minn=read;
    char op;
    int k;
    for(int i=1;i<=n;i++){
        cin>>op;k=read;
        switch(op){
            case 'I':
                if(k>=minn)
                    insert(k-add),++sum;
                break;
            case 'A':
                add+=k;
                break;
            case 'S':
                add-=k;
                del(minn-add);
                break;
            case 'F':
                if(siz(rt)

\(T_E\) 文藝平衡樹

平衡樹不僅具有二叉搜索樹的功能，同樣可以支持區(qū)間操作，即，將序列的下標(biāo)塞進(jìn)平衡樹，它的中序遍歷就是原序列，然后我們想干嘛就干嘛~

對于區(qū)間翻轉(zhuǎn)，考慮維護(hù)懶標(biāo)記，下放時(shí)交換左右兒子，分別異或。最后中序遍歷輸出每個(gè)節(jié)點(diǎn)的值。

對于打懶標(biāo)記，分裂出 \([l,r]\) 部分，一定要先分出前 \(r\) 個(gè)，再分前 \(l-1\) 個(gè)，反過來如果先分前 \(l-1\) 個(gè)，后面就應(yīng)該分出 \(r-l+1\) 個(gè)，手畫一下就知道為什么了。

這里使用 \(\tt{FHQ\_ Treap}\) 時(shí)，我們按子樹大小進(jìn)行分裂，因?yàn)槲覀兪前凑障聵?biāo)建的樹，不能按權(quán)值分裂。

FHQ_Treap 
#include
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n,m;

namespace FHQ_TREAP{
    struct Treap{
        int son[2],val,cnt,siz,rd,lazy;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
        #define lazy(i) t[i].lazy
    }t[N];
    int tot,rt;
    int New(int k){
        val(++tot)=k;
        cnt(tot)=siz(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void down(int i){
        if(!lazy(i))  return;
        swap(ls(i),rs(i));
        lazy(ls(i))^=1;
        lazy(rs(i))^=1;
        lazy(i)=0;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        down(i);
        if(siz(ls(i))+cnt(i)<=k)  x=i,split(rs(i),k-(siz(ls(i))+cnt(i)),rs(i),y);
        else  y=i,split(ls(i),k,x,ls(i));
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  down(x),merge(rs(x),rs(x),y),i=x;
        else  down(y),merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void out(int i){
        down(i);
        if(ls(i))  out(ls(i));
        write(val(i));putchar(' ');
        if(rs(i))  out(rs(i));
    }
} using namespace FHQ_TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    srand(time(0));
    n=read,m=read;
    for(int i=1;i<=n;i++)  insert(i);
    int l,r,rt1,rt2,rt3;
    for(int i=1;i<=m;i++){
        l=read,r=read;
        rt1=rt2=rt3=0;
        split(rt,r,rt1,rt3);
        split(rt1,l-1,rt1,rt2);
        lazy(rt2)^=1;
        merge(rt1,rt1,rt2);
        merge(rt,rt1,rt3);
        // split(rt,l-1,rt1,rt2);
        // split(rt2,r-l+1,rt2,rt3);
        // lazy(rt2)^=1;
        // merge(rt2,rt2,rt3);
        // merge(rt,rt1,rt2);
    }
    out(rt);
    return 0;
}

對于 \(\tt{Splay}\) ，其實(shí)是差不多的，我們都是將區(qū)間轉(zhuǎn)到一棵子樹上進(jìn)行打標(biāo)記，類似于刪除操作，我們將 \(l-1\) 轉(zhuǎn)到根，將 \(r+1\) 轉(zhuǎn)到根的兒子，那么 \(ls(rs(rt))\) 的子樹就是區(qū)間 \([l,r]\) ，然后和 \(\tt{FHQ}\) 一樣。

我的代碼比較排斥 \(0\) ，所以我干脆將整體 \(+1\) ，最后答案 \(-1\) 輸出。

Splay 
#include
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n,m;

namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,lazy,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define lazy(i) t[i].lazy
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+1;
    }
    void down(int i){
        if(!lazy(i))  return;
        lazy(i)=0;
        swap(ls(i),rs(i));
        lazy(ls(i))^=1,lazy(rs(i))^=1;
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[rs(z)==y]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            down(x);
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    int find(int k){
        if(!rt)  return 0;
        int p=rt;
        while(siz(ls(p))+1!=k){
            if(k<=siz(ls(p)))
                p=ls(p);
            else{
                k-=(siz(ls(p))+1);
                p=rs(p);
            }
            down(p);
        }
        return p;
    }
    void insert(int &i,int f,int x,int k){
        if(!i){
            i=++tot;
            siz(i)=1;fa(i)=f;val(i)=k;
            return;
        }
        if(x<=siz(ls(i))+1)  insert(ls(i),i,x,k);
        else  insert(rs(i),i,x-siz(ls(i))-1,k);
        up(i);
    }
    void out(int i){
        down(i);
        if(ls(i))  out(ls(i));
        if(val(i)>1&&val(i)<=n+1)
        write(val(i)-1),putchar(' ');
        if(rs(i))  out(rs(i));
    }
} using namespace SPLAY;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    insert(rt,0,1,1);
    for(int i=1;i<=n;i++){
        insert(rt,0,i+1,i+1);
        splay(tot,0);
    }
    insert(rt,0,n+2,n+2);
    int l,r;
    for(int i=1;i<=m;i++){
        l=read+1,r=read+1;
        splay(find(l-1),0);
        splay(find(r+1),rt);
        int p=ls(rs(rt));
        lazy(p)^=1;
    }
    out(rt);
    return 0;
}

\(T_F\) 二逼平衡樹

線段樹套平衡樹板子。

  • 首先建立普通線段樹，對于每個(gè)區(qū)間建一棵平衡樹。
  • 對于 \(x\) 區(qū)間內(nèi)排名，轉(zhuǎn)化成查找區(qū)間內(nèi)比它小的樹的個(gè)數(shù)加 \(1\) ，分裂求。
  • 對于第 \(k\) 小數(shù)，考慮二分，通過操作 \(1\) 檢查
  • 單點(diǎn)修改直接從根節(jié)點(diǎn)跑到葉子，路過的每個(gè)節(jié)點(diǎn)都要?jiǎng)h掉原數(shù)，插入新數(shù)。注意要修改原序列。
  • 前驅(qū)后繼直接分別查區(qū)間內(nèi)每個(gè)小區(qū)間，取極值即可。

由于難寫難調(diào)，只打了 FHQ_Treap

FHQ_Treap 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 5*1e4+10;
const int inf = 2147483647;
int n,a[N],m;
int MIN=inf,MAX=-inf;

namespace FHQ_TREAP{
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N<<6];
    int tot;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    int New(int k){
        val(++tot)=k;
        siz(tot)=cnt(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
        else  y=i,split(ls(i),k,x,ls(i));
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int &rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void del(int &rt,int k){
        int rt1,rt2,cut;
        split(rt,k,rt1,rt2);
        split(rt1,k-1,rt1,cut);
        merge(cut,ls(cut),rs(cut));
        merge(rt1,rt1,cut);
        merge(rt,rt1,rt2);
    }
    int sumless(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        int res=siz(rt1);
        merge(rt,rt1,rt2);
        return res;
    }
    int pre(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        if(!siz(rt1))  return -inf;
        int res=rt1;
        while(rs(res))  res=rs(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    int nxt(int rt,int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        if(!siz(rt2))  return inf;
        int res=rt2;
        while(ls(res))  res=ls(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    #undef ls
    #undef rs
};
using namespace FHQ_TREAP;

namespace Segment_Tree{
    struct SegTree{
        int l,r,rt;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define rt(i) tr[i].rt
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        for(int k=l;k<=r;k++){
            insert(rt(i),a[k]);
        }
        if(l==r)  return;
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
    }
    int lessk(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return sumless(rt(i),k);
        }
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res+=lessk(ls(i),ql,qr,k);
        if(mid>1;
            if(q_rk(ql,qr,mid)<=k)
                res=mid,st=mid+1;
            else  ed=mid-1;
        }
        return res;
    }
    void modify(int i,int x,int k){
        del(rt(i),a[x]);
        insert(rt(i),k);
        int l=l(i),r=r(i);
        if(l==r)  return;
        int mid=(l+r)>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
    }
    int q_pre(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return pre(rt(i),k);
        }
        int mid=(l+r)>>1,res=-inf;
        if(ql<=mid) res=max(res,q_pre(ls(i),ql,qr,k));
        if(mid>1,res=inf;
        if(ql<=mid)  res=min(res,q_nxt(ls(i),ql,qr,k));
        if(mid0){
        op=read;
        switch(op){
            case 1:
                l=read,r=read,x=read;
                write(q_rk(l,r,x)),pt;break;
            case 2:
                l=read,r=read,x=read;
                write(q_kth(l,r,x)),pt;break;
            case 3:
                l=read,x=read;//不要忘記修改原序列
                modify(1,l,x);a[l]=x;break;
            case 4:
                l=read,r=read,x=read;
                write(q_pre(1,l,r,x)),pt;break;
            case 5:
                l=read,r=read,x=read;
                write(q_nxt(1,l,r,x)),pt;break;
            default:break;
        }
    }
    return 0;
}

服了，洛谷數(shù)據(jù)太強(qiáng)大，我的常數(shù)也太強(qiáng)大，不得不寫離散化。。

FHQ_Treap+離散化 
#include
#define getchar() getchar_unlocked()
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 5*1e4+10;
const int inf = 2147483647;
int n,a[N],m;
int MIN=inf,MAX=-inf;
int lsh[N<<1],num,tt;
int op[N];
int l[N],r[N],x[N];
int ans[N],total;

namespace FHQ_TREAP{
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N<<6];
    int tot;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    int New(int k){
        val(++tot)=k;
        siz(tot)=cnt(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
        else  y=i,split(ls(i),k,x,ls(i));
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int &rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void del(int &rt,int k){
        int rt1,rt2,cut;
        split(rt,k,rt1,rt2);
        split(rt1,k-1,rt1,cut);
        merge(cut,ls(cut),rs(cut));
        merge(rt1,rt1,cut);
        merge(rt,rt1,rt2);
    }
    int sumless(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        int res=siz(rt1);
        merge(rt,rt1,rt2);
        return res;
    }
    int pre(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        if(!siz(rt1))  return -inf;
        int res=rt1;
        while(rs(res))  res=rs(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    int nxt(int rt,int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        if(!siz(rt2))  return inf;
        int res=rt2;
        while(ls(res))  res=ls(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    #undef ls
    #undef rs
};
using namespace FHQ_TREAP;

namespace Segment_Tree{
    struct SegTree{
        int l,r,rt;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define rt(i) tr[i].rt
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        for(int k=l;k<=r;k++){
            insert(rt(i),a[k]);
        }
        if(l==r)  return;
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
    }
    int lessk(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return sumless(rt(i),k);
        }
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res+=lessk(ls(i),ql,qr,k);
        if(mid>1;
            if(q_rk(ql,qr,mid)<=k)
                res=mid,st=mid+1;
            else  ed=mid-1;
        }
        return res;
    }
    void modify(int i,int x,int k){
        del(rt(i),a[x]);
        insert(rt(i),k);
        int l=l(i),r=r(i);
        if(l==r)  return;
        int mid=(l+r)>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
    }
    int q_pre(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return pre(rt(i),k);
        }
        int mid=(l+r)>>1,res=-inf;
        if(ql<=mid) res=max(res,q_pre(ls(i),ql,qr,k));
        if(mid>1,res=inf;
        if(ql<=mid)  res=min(res,q_nxt(ls(i),ql,qr,k));
        if(mid

\(T_G\) JSOI2008火星人prefix

平衡樹維護(hù)序列， \(\tt{FHQ}\) 按子樹大小分裂，維護(hù) \(hash\) 值，父節(jié)點(diǎn)存子樹的 \(hash\) 值，最后二分求 \(LCP\) 。注意插入字符后要 ++n 。

還是 \(\tt{FHQ}\) 好打， \(\tt{Splay}\) 以后再說。

FHQ_Treap 
#include
using namespace std;
#define  ull unsigned long long
#define read read()
#define pt puts("")
#define gc getchar
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 100010
const ull base = 233;

int n,m;
char s[N];

ull pb[N];
void init(){pb[0]=1ull;for(int i=1;ird(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int x,int k){
        int rt1,rt2;
        split(rt,x,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void replace(int x,int k){
        int rt1,rt2,rt3;
        split(rt,x,rt1,rt2);
        split(rt1,x-1,rt1,rt3);
        merge(rt1,rt1,New(k));
        merge(rt,rt1,rt2);
    }
    ull q_hash(int l,int r){
        int rt1,rt2,rt3;
        split(rt,r,rt2,rt3);
        split(rt2,l-1,rt1,rt2);
        ull res=hash(rt2);
        merge(rt2,rt1,rt2);
        merge(rt,rt2,rt3);
        return res;
    }
} using namespace FHQ_Treap;

int solve(int l,int r){
    int st=0,ed=n-r+1;
    int res=0;
    while(st<=ed){
        int mid=(st+ed)>>1;
        if(q_hash(l,l+mid-1)==q_hash(r,r+mid-1)){
            st=mid+1;res=mid;
        }
        else  ed=mid-1;
    }
    return res;
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    scanf("%s",s+1);
    n=strlen(s+1);m=read;
    init();
    for(int i=1;i<=n;i++){
        insert(i-1,s[i]-'a'+1);
    }
    char op,x;
    int l,r;
    while(m-->0){
        op=gc();while(op!='Q'&&op!='R'&&op!='I')op=gc();
        switch(op){
            case 'Q':
                l=read,r=read;
                write(solve(l,r)),pt;
                break;
            case 'R':
                l=read;x=gc();while(x<'a'||x>'z')  x=gc();
                replace(l,x-'a'+1);
                break;
            case 'I':
                l=read;x=gc();while(x<'a'||x>'z')  x=gc();
                insert(l,x-'a'+1);++n;
                break;
            default:break;
        }
    }

    return 0;
}

\(T_H\) 最長上升子序列

逆天性質(zhì)題~~

本來對于 \(dp_i\) 表示以 \(i\) 位置結(jié)尾的最長上升子序列長度，有:

但是對于此題，他是按照 \(1\) ~ \(n\) 的順序插入，也就是，當(dāng)前插入的數(shù)，一定比原序列里所有數(shù)都大，那么

考慮平衡樹維護(hù)序列，節(jié)點(diǎn)存子樹里的 \(dp\) 最大值，直接轉(zhuǎn)移即可。

  • 對于 \(\tt{FHQ}\) ，分裂出前 \(i\) 個(gè)， \(rt1\) 的 \(dp\) 值 \(\tt{+1}\) 即為所求
  • 對于 \(\tt{Splay}\) ，轉(zhuǎn)到根節(jié)點(diǎn)，左兒子的 \(dp\) 值 \(\tt{+1}\) 即為所求
FHQ_Treap 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;

namespace FHQ_Treap{
    struct Treap{
        int son[2],rd,siz,len,ans;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define siz(i) t[i].siz
        #define len(i) t[i].len
        #define ans(i) t[i].ans
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+1;
        ans(i)=max(ans(ls(i)),ans(rs(i)));
        ans(i)=max(ans(i),len(i));
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(k<=siz(ls(i)))  y=i,split(ls(i),k,x,ls(i));
        else  x=i,split(rs(i),k-(siz(ls(i))+1),rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    int New(int k){
        ++tot;
        siz(tot)=1;
        ans(tot)=len(tot)=k;
        rd(tot)=rand();
        return tot;
    }
    void insert(int x){
        int rt1,rt2;
        split(rt,x,rt1,rt2);
        merge(rt,rt1,New(ans(rt1)+1));
        merge(rt,rt,rt2);
    }

} using namespace FHQ_Treap;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    for(int x,i=1;i<=n;i++){
        x=read;
        insert(x);
        write(ans(rt));pt;
    }
    return 0;
}
Splay 
#include
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;

namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,ans,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define siz(i) t[i].siz
        #define ans(i) t[i].ans
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+1;
        ans(i)=max(ans(ls(i)),ans(rs(i)));
        ans(i)=max(ans(i),val(i));
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void find(int x){
        if(!rt)  return;
        int p=rt;
        while(siz(ls(p))+1!=x){
            if(x<=siz(ls(p))+1){
                p=ls(p);
            }
            else{
                x-=(siz(ls(p))+1);
                p=rs(p);
            }
        }
        splay(p,0);
    }
    void insert(int &i,int f,int x,int k){
        if(!i){
            i=++tot;
            fa(i)=f;
            siz(i)=1;
            ans(i)=val(i)=k;
            return;
        }
        if(x<=siz(ls(i))+1)  insert(ls(i),i,x,k);
        else  insert(rs(i),i,x-siz(ls(i))-1,k);
        up(i);
    }
    
} using namespace SPLAY;


signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    for(int x,k,i=1;i<=n;i++){
        x=read;
        if(!x)  k=1;
        else if(x==i-1)  k=ans(rt)+1;
        else{
            find(x+1);
            k=ans(ls(rt))+1;
        }
        insert(rt,0,x+1,k);
        splay(tot,0);
        write(ans(rt));pt;
    }
    return 0;
}

\(T_I\) 星系探索

好像是閹割版的 \(\tt{ETT/LCT}\) ( Wang54321 說的)，不會(huì)。

伍.閑話

轉(zhuǎn)眼間在奧賽班的短短 \(3\) 個(gè)月只剩最后幾天，整個(gè)下午跑機(jī)房，還能有多長時(shí)間。。。 \(3\) 個(gè)月說長不長說短不短，學(xué)到了不少東西，雖然不像別的奧賽對高中文化課有很大幫助，但是:

我們學(xué)的東西是他們這輩子都不一定能接觸到的。。。

不知道回原班在中考前還能學(xué)多長時(shí)間 \(\tt{OI}\) ，像小 \(\tt{H}\) 說的

也不知道回原班之后的二三十天，自己還能在這個(gè)機(jī)位上坐幾個(gè)小時(shí)。這種感覺，或有點(diǎn)像心有余而力不足而被迫退役的感覺吧。當(dāng)然我也希望，兩年后的自己，不會(huì)有這種感覺�！� \(\tt{HANGRY\_ Sol}\)

沒想到二模完沒有立刻【垃圾分類】，那就把 \(\tt{Splay}\) 收尾，不用放假加班了，珍惜機(jī)房的每一分鐘吧...

小編推薦閱讀

好特網(wǎng)發(fā)布此文僅為傳遞信息，不代表好特網(wǎng)認(rèn)同期限觀點(diǎn)或證實(shí)其描述。

相關(guān)視頻攻略

更多

掃二維碼進(jìn)入好特網(wǎng)手機(jī)版本！

掃二維碼進(jìn)入好特網(wǎng)微信公眾號！

本站所有軟件，都由網(wǎng)友上傳，如有侵犯你的版權(quán)，請發(fā)郵件[email protected]

湘ICP備2022002427號-10 湘公網(wǎng)安備：43070202000427號© 2013~2025 haote.com 好特網(wǎng)