题解 P3369 【模板】普通平衡树

题意描述

链接

实现插入、删除、查找排名、查找第 $k$ 大、查找前驱、后继。

很明显的平衡树，但是这里我介绍一种非常规做法——分块。

虽然是 $n\sqrt{n}$ 做法，但是依据数据范围还是可以过的。

做法

首先我们需要处理一个难点：插入。因为一般的分块都是根据数组来实现，所以仅仅是插入就需要 $O(n)$ 的时间复杂度，并且会给维护带来一定的麻烦，这是所不能允许的。

所以需要上另外一种数据结构——链表。链表支持 $O(1)$ 插入/删除。

但是还有 $O(n)$ 的查询怎么办？这时候就需要用到分块了。

先令最大块长为 $L$。

我们可以开两个链表 $l1$ 和 $l2$，分别存每个块的第一个数在 $l2$ 的位置和所维护的一些数。

另外，$l2$ 中的数需要按升序排序。

下面是链表具体存的东西

struct sss
{
    int v,mn,pos,nxt,pre;
    sss(int a,int s,int f){v=a;mn=s;pos=f;}
    sss(){pre=nxt=v=pos=0;mn=1e9;}
    // v在l1中是块中的元素个数，在l2中是元素具体的值
    // mn是最小值
    // pos是每个块的第一个数在l2的位置
    // nxt和pre分别是链表的下一个数和上一个数
}a[1000005];

PS：其实并没有必要存 $mn$，因为 $l2$ 是升序排序的，所以每个块的最小值一定是每个块的第一个数，但是当时写的时候并没有多想。

下面是具体的操作：

插入

设插入的数为 $key$。

首先我们特判一下当前的链表是否为空，如果是，那么我们就直接将这个数插进去。

否则我们就在 $l1$ 上面跳，直到我们找到一个 $p$，使得 $mn_p \le key$ 且 $mn_{p+1}>key$。

然后我们再在 $l2$ 上面跳，找到一个位置 $q$，使得 $q$ 的的值为最大的小于 $key$ 的。

然后把 $key$ 插入 $q$ 的后面，同时更新一下 $p$ 的 $v$ 和 $mn$，同时需要注意的是：如果 $key$ 是插在块首，还应该更新一下 $p$ 的 $pos$ 信息。

单次操作期望复杂度 $O(\sqrt{n})$。

Code

void insert(int key)
{
    if(l1.a[l1.head].nxt==l1.tail)
    {
        l2.insert(l2.head,{key,key,0});
        l1.insert(l1.head,{1,key,l2.cnt});
        return;
    }
    int p=l1.head;
    for(int i=l1.head;i!=l1.tail;i=l1.a[i].nxt)
    {
        if(l1.a[i].mn>key)break;
        p=i;
    }
    if(p==l1.head)p=l1.a[l1.head].nxt;//特判p在链首或链尾
    if(p==l1.tail)p=l1.a[l1.tail].pre;
    int q=l2.a[l1.a[p].pos].pre;
    for(int i=l1.a[p].pos;i!=l1.a[l1.a[p].nxt].pos;i=l2.a[i].nxt)
    {
        if(l2.a[i].v>key)break;
        q=i;
    }
    l2.insert(q,{key,key,0});
    if(l2.a[q].nxt==l2.a[l1.a[p].pos].pre)l1.a[p].pos=l2.a[q].nxt;//特判块首
    l1.a[p].v++;
    l1.a[p].mn=min(key,l1.a[p].mn);
    if(l1.a[p].v>=2*L)split(p);//这个下面讲
}

但是问题来了，万一出题人造数据时将插入全放在同一个块里，这样单次操作的复杂度会退化成 $O(n)$，这样会过不去。

所以就需要另外一种操作：分裂。

分裂

顾名思义，分裂就是将一个块分裂成两个，至于什么时候分裂，可以在该块长大于 $L$ 时分裂，也可以在该块长大于等于 $2L$ 时分裂，总之在这道题里面没有影响。

设要分裂的块为 $pos$。

我们可以遍历 $pos$，另外预先开下面几个变量：

$j$：存储当前的数是块中第几个；
$z$：存储第一个块的信息；
$x$：存储第二个块的信息。

当 $j\le L$ 时，更新 $z$。

否则更新 $x$。

然后将 $pos$ 修改成 $z$，在 $pos$ 后插入 $x$。

Code

void split(int pos)
{
    lst::sss z,x;
    for(int i=l1.a[pos].pos,j=1;i!=l1.a[l1.a[pos].nxt].pos;i=l2.a[i].nxt,j++)
    {//遍历pos
        if(j<=L)
        {
            if(!z.pos)z.pos=i;//判断块首
            z.mn=min(z.mn,l2.a[i].v);
            z.v++;
        }
        else
        {
            if(!x.pos)x.pos=i;//判断块首
            x.mn=min(x.mn,l2.a[i].v);
            x.v++;
        }
    }
    z.pre=l1.a[pos].pre;//别把pre和nxt给改了
    z.nxt=l1.a[pos].nxt;
    l1.a[pos]=z;
    l1.insert(pos,x);
}

删除

~~其实后面的操作就只需要在插入上面改改就行了~~

设删除的数为 $key$。

同插入，我们需要找到 $key$ 的位置并删除即可。

需要注意的是：

依然需要特判块首
如果块 $p$ 为空的话，需要将其删除

Code

void remove(int key)
{
    int p=l1.head;
    for(int i=l1.head;i!=l1.tail;i=l1.a[i].nxt)
    {
        if(l1.a[i].mn>key)break;
        p=i;
    }
    if(p==l1.head)p=l1.a[l1.head].nxt;
    if(p==l1.tail)p=l1.a[l1.tail].pre;
    int q=l2.a[l1.a[p].pos].pre;
    for(int i=l1.a[p].pos;i!=l1.a[l1.a[p].nxt].pos;i=l2.a[i].nxt)
    {
        if(l2.a[i].v>key)break;
        if(l2.a[i].v==key){q=i;break;}
        q=i;
    }
    if(q==l1.a[p].pos)l1.a[p].pos=l2.a[q].nxt,l1.a[p].mn=l2.a[l1.a[p].pos].v;
    //特判块首
    l1.a[p].v--;
    if(!l1.a[p].v)l1.remove(p);//删除p
    l2.remove(q);
}

查询排名

设要查询的值是 $key$。

先开一个变量为 $ans$。

同样地，先找到最后一个小于 $key$ 的数的位置。

并且在找的过程中，需要将记录在 $key$ 前面的数的个数（一路累加即可）。

注意如果 $p$ 在特判前不是 $head$，$ans$ 要减去 $p$ 的 $v$（因为算重了）。

最后返回 $ans+1$ 即可。

Code

int v2r(int key)
{
    int p=l1.head,ans=0;
    for(int i=l1.head;i!=l1.tail;i=l1.a[i].nxt)
    {
        if(l1.a[i].mn>=key)break;
        ans+=l1.a[i].v;
        p=i;
    }
    if(p==l1.tail)p=l1.a[l1.tail].pre;
    ans-=l1.a[p].v;//去重
    if(p==l1.head)p=l1.a[l1.head].nxt;
    for(int i=l1.a[p].pos;i!=l1.a[l1.a[p].nxt].pos;i=l2.a[i].nxt)
    {
        if(l2.a[i].v>=key)break;
        ans++;
    }
    return ans+1;
}

查询第 $k$ 大

设要查询的排名是 $pos$。

然后还是先在块上跳，跳完之后再在块里面跳。

过程可以类比 FHQ 的按排名分裂。

Code

int r2v(int pos)
{
    int p=l1.head;
    for(int i=l1.head;i!=l1.tail;i=l1.a[i].nxt)
    {
        p=i;
        if(l1.a[i].v>=pos)break;
        pos-=l1.a[i].v;
    }
    if(p==l1.head)p=l1.a[l1.head].nxt;
    if(p==l1.tail)p=l1.a[l1.tail].pre;
    int q=l2.a[l1.a[p].pos].pre;
    for(int i=l1.a[p].pos;i!=l1.a[l1.a[p].nxt].pos;i=l2.a[i].nxt)
    {
        if(!pos)break;v
        q=i;
        pos--;
    }
    return l2.a[q].v;
}

前驱

设要查询的值是 $key$。

跟查询排名相似，只不过返回的不是排名而是最后一个小于 $key$ 的数的值。

Code

int pre(int key)
{
    int p=l1.head;
    for(int i=l1.head;i!=l1.tail;i=l1.a[i].nxt)
    {
        if(l1.a[i].mn>=key)break;
        p=i;
    }
    if(p==l1.head)p=l1.a[l1.head].nxt;
    if(p==l1.tail)p=l1.a[l1.tail].pre;
    int q=l2.a[l1.a[p].pos].pre;
    for(int i=l1.a[p].pos;i!=l1.a[l1.a[p].nxt].pos;i=l2.a[i].nxt)
    {
        if(l2.a[i].v>=key)break;
        q=i;
    }
    return l2.a[q].v;
}

后继

设要查询的值是 $key$。

跟后继相似，但是返回的是第一个大于 $key$ 的值。

Code

int nxt(int key)
{
    int p=l1.head;
    for(int i=l1.head;i!=l1.tail;i=l1.a[i].nxt)
    {
        if(l1.a[i].mn>key)break;
        p=i;
    }
    if(p==l1.head)p=l1.a[l1.head].nxt;
    if(p==l1.tail)p=l1.a[l1.tail].pre;
    int q=l2.a[l1.a[p].pos].pre;
    for(int i=l1.a[p].pos;i!=l1.a[l1.a[p].nxt].pos;i=l2.a[i].nxt)
    {
        if(l2.a[i].v>key)break;
        q=i;
    }
    return l2.a[l2.a[q].nxt].mn;//这里的q是最后一个key的位置
}

初始化

在构造函数里面已经看到，$mn$ 的初值要赋成极大值，否则后面更新的 $mn$ 都是 $0$。

但是 $head$ 的 $mn$ 必须赋成 $0$，否则压根都跑不进去（如果是拿块首当最小值另谈）。

还有 $l2$ 的 $tail$ 的 $v$ 必须赋成 $0$，否则会挂。

Code

void init()
{
    cnt=2;
    head=1;tail=2;
    a[head].mn=0;
    a[head].nxt=tail;
    a[tail].v=1e9;
}//链表内初始化

void init(){l1.init();l2.init();}//链表外初始化

块长

令块长为 $L=\sqrt{n}$。

确定 $n$ 有三种方法：

直接以操作数为 $n$，能过，但是跑得较慢；
以插入操作的数量为 $n$，跑得比较快。
将操作离线下来，开一个变量储存最多会维护多少个数，以最大值为 $n$，比第二种稍微快个几十毫秒。

综上建议直接以插入操作的数量为 $n$。

后记

核心代码都在上面给了，完整代码就不放了。

写完之后才发现这个东西其实叫块状链表。

码量比我的二逼平衡树还大，极度不推荐。