网站导航

您的位置：首页 > 软件教程 > 教程 > 平衡树 Treap & Splay [学习笔记]

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

来源：好特整理　|　时间：2024-05-25 09:45:58 |　阅读：62　|　 标签： T Play S 平衡 EA 　 |　分享到：

平衡树 \(\tt{Treap}\) & \(\tt{Splay}\) 壹.单旋 \(\tt{Treap}\) 首先了解 \(\tt{BST}\) 非常好用的东西，但是数据可以把它卡成一条链 \(\dots\) 于是，我们将 \(\tt{Tree}\) 与 \(\tt{heap}\) (堆)

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

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

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

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

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

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

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

K8He的图

以右旋为例，我们发现，本来的中序遍历顺序为 \(y ，那么对于 \(q\) 右旋，即将左儿子旋上来，由于本来 \(p ，所以显然 \(q\) 要成为 \(p\) 的右儿子。那就剩下 \(x\) 无家可归，我们发现 \(p ，那么 \(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].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].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;
    }
}
  • 前驱后继，和普通 \(\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\) 单旋一次上去

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

    • \(x,y,z\) 三点共线，即

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

    此时我们应先转 \(y\) 再转 \(x\)

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

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

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

就这样旋旋旋，就能保证深度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)
    • 按照子树大小插入，可以递归写(爱咋写咋写) 
    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)
    • 子树大小 
    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
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\) 营业额统计

板子，求前驱后继。

普通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\) 宠物收养所

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

普通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\) 求前驱后继时 如果要取等注意特判 ，删除时不可取等(取等就寄了)

\(T_C\) 郁闷的出纳员

维护整体懒标记，每次删除低于 \(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\) 文艺平衡树

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

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

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

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

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}\) ，其实是差不多的，我们都是将区间转到一棵子树上进行打标记，类似于删除操作，我们将 \(l-1\) 转到根，将 \(r+1\) 转到根的儿子，那么 \(ls(rs(rt))\) 的子树就是区间 \([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\) 二逼平衡树

线段树套平衡树板子。

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

由于难写难调，只打了 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;
}

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

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

平衡树维护序列， \(\tt{FHQ}\) 按子树大小分裂，维护 \(hash\) 值，父节点存子树的 \(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\) 最长上升子序列

逆天性质题~~

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

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

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

  • 对于 \(\tt{FHQ}\) ，分裂出前 \(i\) 个， \(rt1\) 的 \(dp\) 值 \(\tt{+1}\) 即为所求
  • 对于 \(\tt{Splay}\) ，转到根节点，左儿子的 \(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 说的)，不会。

伍.闲话

转眼间在奥赛班的短短 \(3\) 个月只剩最后几天，整个下午跑机房，还能有多长时间。。。 \(3\) 个月说长不长说短不短，学到了不少东西，虽然不像别的奥赛对高中文化课有很大帮助，但是:

我们学的东西是他们这辈子都不一定能接触到的。。。

不知道回原班在中考前还能学多长时间 \(\tt{OI}\) ，像小 \(\tt{H}\) 说的

也不知道回原班之后的二三十天，自己还能在这个机位上坐几个小时。这种感觉，或有点像心有余而力不足而被迫退役的感觉吧。当然我也希望，两年后的自己，不会有这种感觉。—— \(\tt{HANGRY\_ Sol}\)

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

小编推荐阅读

好特网发布此文仅为传递信息，不代表好特网认同期限观点或证实其描述。

相关视频攻略

更多

同类最新

更多

热门资讯

更多

  • 游戏推荐
  • 相关版本

更多
  • 资讯
  • 视频

更多
  • 安卓热榜
  • 苹果热榜

关于好特　联系我们　最近更新　本站声明　软件分类　推荐排行

频道 　视频　评测　专题　网游　安卓　礼包　app下载

推荐 　原创　佳游月榜　新游周刊　好特播报

热门 　角色　动作　卡牌 　射击　空战　竞速　音乐

扫二维码进入好特网手机版本！

扫二维码进入好特网微信公众号！

本站所有软件，都由网友上传，如有侵犯你的版权，请发邮件[email protected]

湘ICP备2022002427号-10 湘公网安备：43070202000427号© 2013~2024 haote.com 好特网