平衡树 Treap & Splay [学习笔记]

技术分享 2年前 (2024-05-26) 0 999+

关注

平衡树 (tt{Treap}) & (tt{Splay})

壹.单旋 (tt{Treap})

首先了解 (tt{BST})

非常好用的东西，但是数据可以把它卡成一条链 (dots)

于是，我们将 (tt{Tree}) 与 (tt{heap}) (堆) 合并，以保证平衡树 (log) 的深度。

具体地，我们可以使用旋转操作实现

~~K8He的图~~

以右旋为例，我们发现，本来的中序遍历顺序为 (y<p<x<q<z<r)，那么对于 (q) 右旋，即将左儿子旋上来，由于本来 (p<q) ，所以显然 (q) 要成为 (p) 的右儿子。那就剩下 (x) 无家可归，我们发现 (p<x<q)，那么 (q) 的左儿子再适合不过了。

我们规定 (0) 方向为左，(1) 方向为右，即可通过 (d) ^ (1) 实现方向取反。

一般的，对于一个节点 (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; }

那么我们什么时候进行旋转呢？还记得我们说过要利用堆的性质，那么我们对每个节点随机一个优先级，将它按照小根堆或大根堆存，若当前不满足堆的性质了，那就旋转。

插入操作，从根往下跑，但要注意不满足堆的性质时，考虑旋转。

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].val<k);     insert(t[i].son[d],k);     if(t[i].rd>t[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].val<k;     del(t[i].son[d],k);     return; }

查排名，看代码理解即可。

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)  return t[ls(i)].siz+t[i].cnt+rk(rs(i),k);     return t[ls(i)].siz+1; }

查第 (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;     } }

前驱后继，和普通 (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})，我们只需要理解旋转操作即可，毕竟下面的 (tt{Splay}) 还要用它，请务必看懂旋转操作，其他的，~~还是FHQ好打，~~ 差不多看看就行，应用范围不大。

(板子封装在下面题单 普通平衡树 里)

贰.无旋 (tt{FHQ Treap})

由于单旋 (tt{Treap}) 不好打且扩展功能不多，所以我们引入新的 (tt{FHQ_ Treap})，好像是神范浩强发明的，%%%%%%。

~~网上都说FHQ比单旋好理解，我表示理解了之后确实好理解，但你得先理解(我看了一个多小时才看懂，不过我是fw)~~

好那么直入正题 —— (tt{FHQ_ Treap})

既然也是 (tt{Treap})，那就是一样的，也是靠堆性质，它的不同之处就在于，它无旋，它是靠分裂+合并来保证 (log) 的深度。

具体地，分裂方式有两种，一种是按权值分裂，另一种是按照子树大小分裂:

按照权值分裂，比如将以 (i) 为根的平衡树分成两棵平衡树，根分别是 (x,y)，要求树 (x) 的权值都小于等于 (k),剩下是 (y)，那么分讨:
- 如果 (val(i)<=k)，那么 (i) 的整棵左子树一定都小于 (k)，肯定都要划到 (x) 里，则令 (x=i)，继续递归划分 (rs(i)) 即可。
- 否则，(i) 的整棵右子树一定都大于 (k)，肯定都要划到 (y) 里，则令 (y=i)，继续递归划分 (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) 肯定都要划到 (x) 里，则令 (x=i)，继续递归划分 (rs(i)) 即可。
- 否则，(i) 的整棵右子树肯定都要划到 (y) 里，则令 (y=i)，继续递归划分 (ls(i)) 即可。

按子树大小分裂，一般用在平衡树维护序列，后面的 (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); }

下一个操作是合并，(tt{FHQ_ Treap}) 正是通过它保证的堆性质，设要合并的两棵树的根分别为 (x,y)，设堆性质为大根堆。
- 若 (rd(x)>rd(y)) 则把 (x) 定为根，然后继续递归合并 (rs(x)) 和 (y)
- 否则把 (y) 定为根，然后继续递归合并 (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)，合并时把 (k) 合并进去。

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}) 一样。
前驱后继，以前驱为例，分裂出 (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})，它不再依靠随机的优先级保证深度，而是通过不断旋转来达到目的。

类似于单旋，只不过单旋是将某节点的儿子旋上来，而 (tt{Splay}) 是将某节点自身旋上去，单次旋转和 (tt{Treap}) 一样，但是要多记录一个父亲

具体地，旋转 (x) 时，令 (y) 为 (x) 的父亲，(z) 为祖父，设 (x) 为 (y) 在 (d) 方向上的儿子，则单次旋转可分为这几步:

(x) 替换 (y) 成为 (z) 的儿子
(x) 在 (d) ^ (1) 方向的儿子下放给 (y) 当 (d) 方向的儿子
(y) 充当 (x) 在 (d) ^ (1) 方向的儿子

三次修改，三次认爹，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 操作是将节点 (x) 旋转到目标节点 (s) 的儿子，若 (s=0) 则为旋转到根。那么如果我们一直一直单旋上去的话我们会发现一个严重的问题——虽然 (x) 上去了，但是它的最大深度依然没变，也就是说，转了个寂寞。。

那么怎么办，进行双旋，讨论几种情况——((x,y,z) 意义同上)

(z=s) 直接将 (x) 单旋一次上去
(znot ={s})
- (x,y,z) 三点共线，即
此时我们应先转 (y) 再转 (x)

-
- (x,y,z) 三点不共线，直接旋转两次 (x)
-

就这样旋旋旋，就能保证深度OK，每次插入节点后都要进行一次 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; }

至于这么旋为什么可以让复杂度OK，使用什么"势能分析法"，我是fw我不会。

(tt{Splay}) 与 (tt{FHQ}) 一样，也是两种维护方式，一种维护权值，一种维护下标(即序列的中序遍历)。

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

插入，有两种方式，即按权值和子树大小，与 (tt{FHQ}) 类似，注意要记录一下父亲节点

按照权值插入

void insert(int k){     int p=rt,f=0;     while(p&&val(p)!=k){         f=p;         p=t[p].son[val(p)<k];     }     if(p)  ++cnt(p);     else{         p=++tot;         if(f)  t[f].son[val(f)<k]=p;         val(p)=k;fa(p)=f;         siz(p)=cnt(p)=1;     }     splay(p,0); }

按照子树大小插入，可以递归写(爱咋写咋写)

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，我们要先找到某权值对应的节点，直接找然后splay

权值

void find(int k){     if(!rt)  return;     int p=rt;     while(t[p].son[val(p)<k]&&val(p)!=k){         p=t[p].son[val(p)<k];     }     splay(p,0); }

子树大小

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}) 同理，不再赘述
查排名，转到根节点后左子树的大小 (+1) 即可
查前驱后继，以前驱为例，转到根之后左子树里最大值即前驱，后继同理
删除比较有意思，我们先找到前驱后继，然后将前驱splay到根，将后继splay到前驱的右儿子，那么要删除的节点就一定为 (ls(rs(rt))) (如下图)。这也就意味着必须有前驱后继，否则删不了，那么直接插入两个极值哨兵节点即可。

     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; }

另外，维护序列的 (tt{Splay}) 进行区间操作时，也是将区间转化为子树,和删除操作类似，比如文艺平衡树就是这样，不再赘述。

最后注意一定要插哨兵

(板子封装在下面题单 普通平衡树 里)

肆.(hs)题单

(T_D) 普通平衡树

由于是纯板子，所以先挂 (T_D)。

普通Treap

#include<bits/stdc++.h> 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].val<k);         insert(t[i].son[d],k);         if(t[i].rd>t[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].val<k;         del(t[i].son[d],k);         return;     }     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)  return t[ls(i)].siz+t[i].cnt+rk(rs(i),k);         return t[ls(i)].siz+1;     }     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;         }     }     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<bits/stdc++.h> 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<bits/stdc++.h> 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]&&val(p)!=k){             p=t[p].son[val(p)<k];         }         splay(p,0);     }     void insert(int k){         int p=rt,f=0;         while(p&&val(p)!=k){             f=p;             p=t[p].son[val(p)<k];         }         if(p)  ++cnt(p);         else{             p=++tot;             if(f)  t[f].son[val(f)<k]=p;             val(p)=k;fa(p)=f;             siz(p)=cnt(p)=1;         }         splay(p,0);     }     int pre(int k){         find(k);int p=rt;         if(val(p)<k)  return p;         p=ls(p);while(rs(p))  p=rs(p);         return p;     }     int nxt(int k){         find(k);int p=rt;         if(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)<k)  return 1;         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 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) 营业额统计

板子，求前驱后继。

普通Treap

#include<bits/stdc++.h> 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)<k);         insert(t[i].son[d],k);         if(rd(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)<k)  return nxt(rs(i),k);         return min(val(i),nxt(ls(i),k));     } } using namespace TREAP;  signed main() {     #ifndef ONLINE_JUDGE         freopen("lty.in","r",stdin);         freopen("lty.out","w",stdout);     #endif     n=read;     a=read;     ans=a;     insert(rt,a);     for(int i=2;i<=n;i++){         a=read;         int prea=pre(rt,a);         int nxta=nxt(rt,a);         ans+=min(a-prea,nxta-a);         insert(rt,a);     }     write(ans);     return 0; }

FHQ_Treap

#include<bits/stdc++.h> 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<bits/stdc++.h> 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]&&val(p)!=k){             p=t[p].son[val(p)<k];         }         splay(p,0);     }     void insert(int k){         int p=rt,f=0;         while(p&&val(p)!=k){             f=p;             p=t[p].son[val(p)<k];         }         if(p)  ++cnt(p);         else{             p=++tot;             if(f)  t[f].son[val(f)<k]=p;             val(p)=k;fa(p)=f;             siz(p)=cnt(p)=1;         }         splay(p,0);     }     int pre(int k){         find(k);int p=rt;         if(val(p)<=k)  return p;         p=ls(p);while(rs(p))  p=rs(p);         return p;     }     int nxt(int k){         find(k);int p=rt;         if(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) 宠物收养所

发现某时刻的平衡树里只会全是人或者全是狗，查前驱后继即可，查完即删。

普通Treap

#include<bits/stdc++.h> 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)<k);         insert(t[i].son[d],k);         if(rd(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);         --siz(i);         del(t[i].son[d],k);         return;     }     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)<k)  return nxt(rs(i),k);         return min(val(i),nxt(ls(i),k));     } } using namespace TREAP;  int num[2]; bool now,a; int b; int ans; signed main() {     #ifndef ONLINE_JUDGE         freopen("lty.in","r",stdin);         freopen("lty.out","w",stdout);     #endif     n=read;     now=read;     num[now]++;     b=read;insert(rt,b);     for(int i=2;i<=n;i++){         a=read,b=read;         if(!num[a^1]){             num[a]++;insert(rt,b);             now=a;             continue;         }         if(now^a){             int preb=pre(rt,b);             int nxtb=nxt(rt,b);             int hwr=(b-preb<=nxtb-b?preb:nxtb);             ans=(ans+abs(hwr-b))%p;             del(rt,hwr);             --num[now];         }         else             insert(rt,b),++num[now];     }     write(ans);     return 0; }

Splay

#include<bits/stdc++.h> 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];         }         if(p)  ++cnt(p);         else{             p=++tot;             if(f)  t[f].son[val(f)<k]=p;             val(p)=k;fa(p)=f;             siz(p)=cnt(p)=1;         }         splay(p,0);     }     void find(int k){         if(!rt)  return;         int p=rt;         while(t[p].son[val(p)<k] && val(p)!=k){             p=t[p].son[val(p)<k];         }         splay(p,0);     }     int pre(int k,bool b){         find(k);int p=rt;         if(val(p)==k&&b)  return p;         if(val(p)<k)  return p;         p=ls(p);while(rs(p))  p=rs(p);         return p;     }     int nxt(int k,bool b){         find(k);int p=rt;         if(val(p)==k&&b)  return p;         if(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) 求前驱后继时如果要取等注意特判，删除时不可取等(取等就寄了)

(T_C) 郁闷的出纳员

维护整体懒标记，每次删除低于 (minn-add) 线的。

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

服了，(tt{FHQ_ Treap}) 跑不过普通 (tt{Treap}) 的暴力。。。

普通Treap

#include<bits/stdc++.h> 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].val<k);         insert(t[i].son[d],k);         if(t[i].rd>t[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].val<k);         del(t[i].son[d],k);         return;     }     int rk(int i,int k){         if(!i) return 0;         if(t[i].val>k)  return rk(ls(i),k);         if(t[i].val<k)  return t[ls(i)].siz+t[i].cnt+rk(rs(i),k);         return t[ls(i)].siz+1;     }     int find(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;         }     }     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)<k)  ans=-1;                 else ans=find(rt,siz(rt)-k+1)+add;                 write(ans);pt;                 break;             default:                 break;         }     }     write(num-siz(rt));     return 0; }

FHQ_Treap

#include<bits/stdc++.h> 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)<k)  ans=-1;                 else  ans=kth(rt,siz(rt)-k+1)+add;                 write(ans);pt;                 break;         }     }     write(sum-siz(rt));     return 0; }

(T_E) 文艺平衡树

平衡树不仅具有二叉搜索树的功能，同样可以支持区间操作，即，将序列的下标塞进平衡树，它的中序遍历就是原序列，然后我们想干嘛就干嘛~

对于区间翻转，考虑维护懒标记，下放时交换左右儿子，分别异或。最后中序遍历输出每个节点的值。

对于打懒标记，分裂出 ([l,r]) 部分，一定要先分出前 (r) 个，再分前 (l-1) 个，反过来如果先分前 (l-1) 个，后面就应该分出 (r-l+1) 个，手画一下就知道为什么了。

这里使用 (tt{FHQ_ Treap}) 时，我们按子树大小进行分裂，因为我们是按照下标建的树，不能按权值分裂。

FHQ_Treap

#include<bits/stdc++.h> 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})，其实是差不多的，我们都是将区间转到一棵子树上进行打标记，类似于删除操作，我们将 (l-1) 转到根，将 (r+1) 转到根的儿子，那么 (ls(rs(rt))) 的子树就是区间 ([l,r])，然后和 (tt{FHQ}) 一样。

我的代码比较排斥 (0)，所以我干脆将整体 (+1)，最后答案 (-1) 输出。

Splay

#include<bits/stdc++.h> 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) 二逼平衡树

线段树套平衡树板子。

首先建立普通线段树，对于每个区间建一棵平衡树。
对于 (x) 区间内排名，转化成查找区间内比它小的树的个数加 (1)，分裂求。
对于第 (k) 小数，考虑二分，通过操作 (1) 检查
单点修改直接从根节点跑到叶子，路过的每个节点都要删掉原数，插入新数。注意要修改原序列。
前驱后继直接分别查区间内每个小区间，取极值即可。

~~由于难写难调，只打了 FHQ_Treap~~

FHQ_Treap

#include<bits/stdc++.h> 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<qr)  res+=lessk(rs(i),ql,qr,k);         return res;     }     int q_rk(int ql,int qr,int k){         return lessk(1,ql,qr,k)+1;     }     int q_kth(int ql,int qr,int k){         int st=MIN,ed=MAX,res=0;         while(st<=ed){             int mid=(st+ed)>>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<qr)  res=max(res,q_pre(rs(i),ql,qr,k));         return res;     }     int q_nxt(int i,int ql,int qr,int k){         int l=l(i),r=r(i);         if(ql<=l&&r<=qr){             return nxt(rt(i),k);         }         int mid=(l+r)>>1,res=inf;         if(ql<=mid)  res=min(res,q_nxt(ls(i),ql,qr,k));         if(mid<qr)   res=min(res,q_nxt(rs(i),ql,qr,k));         return res;     } }; using namespace Segment_Tree;  signed main() {     srand(time(0));     #ifndef ONLINE_JUDGE         freopen("lty.in","r",stdin);         freopen("lty.out","w",stdout);     #endif     n=read,m=read;     for(int i=1;i<=n;i++)  a[i]=read,MIN=min(MIN,a[i]),MAX=max(MAX,a[i]);     build(1,1,n);     int op,l,r,x;     while(m-->0){         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; }

服了，洛谷数据太强大，我的常数也太强大，不得不写离散化。。

FHQ_Treap+离散化

#include<bits/stdc++.h> #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<qr)  res+=lessk(rs(i),ql,qr,k);         return res;     }     int q_rk(int ql,int qr,int k){         return lessk(1,ql,qr,k)+1;     }     int q_kth(int ql,int qr,int k){         int st=0,ed=num,res=0;         while(st<=ed){             int mid=(st+ed)>>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<qr)  res=max(res,q_pre(rs(i),ql,qr,k));         return res;     }     int q_nxt(int i,int ql,int qr,int k){         int l=l(i),r=r(i);         if(ql<=l&&r<=qr){             return nxt(rt(i),k);         }         int mid=(l+r)>>1,res=inf;         if(ql<=mid)  res=min(res,q_nxt(ls(i),ql,qr,k));         if(mid<qr)   res=min(res,q_nxt(rs(i),ql,qr,k));         return res;     } }; using namespace Segment_Tree;  void LSH(){     sort(lsh+1,lsh+tt+1);     num=unique(lsh+1,lsh+tt+1)-lsh-1;     for(int i=1;i<=n;i++){         a[i]=lower_bound(lsh+1,lsh+num+1,a[i])-lsh;     } }  signed main() {     srand(time(0));     #ifndef ONLINE_JUDGE         freopen("lty.in","r",stdin);         freopen("lty.out","w",stdout);     #endif     n=read,m=read;     for(int i=1;i<=n;i++)  a[i]=lsh[++tt]=read;     for(int i=1;i<=m;i++){         op[i]=read;         switch(op[i]){             case 1:                 l[i]=read,r[i]=read,x[i]=read;break;             case 2:                 l[i]=read,r[i]=read,x[i]=read;break;             case 3:                 l[i]=read,x[i]=read;                 lsh[++tt]=x[i];break;             case 4:                 l[i]=read,r[i]=read,x[i]=read;                 lsh[++tt]=x[i];break;             case 5:                 l[i]=read,r[i]=read,x[i]=read;                 lsh[++tt]=x[i];break;             default:break;         }     }     LSH();     build(1,1,n);     for(int i=1;i<=m;i++){         int an;         switch(op[i]){             case 1:                 x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;                 ans[++total]=q_rk(l[i],r[i],x[i]);break;             case 2:                 ans[++total]=lsh[q_kth(l[i],r[i],x[i])];break;             case 3:                 x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;                 modify(1,l[i],x[i]);a[l[i]]=x[i];break;             case 4:                 x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;                 an=q_pre(1,l[i],r[i],x[i]);                 ans[++total]=(an==-inf?-inf:lsh[an]);break;             case 5:                 x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;                 an=q_nxt(1,l[i],r[i],x[i]);                 ans[++total]=(an==inf?inf:lsh[an]);break;             default:break;         }     }     for(int i=1;i<=total;i++)  write(ans[i]),pt;     return 0; }

(T_G) JSOI2008火星人prefix

平衡树维护序列，(tt{FHQ}) 按子树大小分裂，维护 (hash) 值，父节点存子树的 (hash) 值，最后二分求 (LCP)。注意插入字符后要 ++n。

还是 (tt{FHQ}) 好打，(tt{Splay}) 以后再说。

FHQ_Treap

#include<bits/stdc++.h> 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;i<N;i++)pb[i]=pb[i-1]*base;}  namespace FHQ_Treap{     struct Treap{         int son[2],rd,siz,val;         ull hash;         #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 val(i) t[i].val         #define hash(i) t[i].hash     }t[N<<1];     int tot,rt;     void up(int i){         siz(i)=1+siz(ls(i))+siz(rs(i));         hash(i)=hash(ls(i))*(pb[siz(rs(i))+1])+val(i)*pb[siz(rs(i))]+hash(rs(i));     }     int New(int k){         val(++tot)=k;         hash(tot)=k;         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(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);     }     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) 最长上升子序列

逆天性质题~~

本来对于 (dp_i) 表示以 (i) 位置结尾的最长上升子序列长度，有:

[dp_i = max_{1leq jleq i}^{a_j<a_i}dp_j + 1 ]

但是对于此题，他是按照 (1) ~ (n) 的顺序插入，也就是，当前插入的数，一定比原序列里所有数都大，那么

[dp_i = max_{1leq jleq i}dp_j + 1 ]

考虑平衡树维护序列，节点存子树里的 (dp) 最大值，直接转移即可。

对于 (tt{FHQ})，分裂出前 (i) 个，(rt1) 的 (dp) 值 (tt{+1}) 即为所求
对于 (tt{Splay})，转到根节点，左儿子的 (dp) 值 (tt{+1}) 即为所求

FHQ_Treap

#include<bits/stdc++.h> 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<bits/stdc++.h> 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; }