题解 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\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 的位置并删除即可。

需要注意的是：

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 有三种方法：

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

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

后记

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

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

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