P2596 [ZJOI2006] 书架

ShieHere · 2023-10-13 19:07:02 · 题解

前言

大家好，我不会平衡树，但是非常喜欢暴力算法，所以我用块状链表过了这道题。

此外，本片题解的所有代码基于一下的设置，所以若是遇上了不认识的东西，多半是这里出来的：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5,MAXT=1e3+514,MAXK=3e2+5;
struct LINK{
    LINK *nxt,*pre;
    ll *LP,id;
}link[MAXT*2];
ll tim,c[MAXT*2][MAXT*2],book[MAXN];
LINK *S,*T;
LINK *newpt(){return &link[++tim];}
void ins(LINK *x,LINK *y,LINK *t){
    x->nxt=y->pre=t;
    t->pre=x;t->nxt=y;
}
void init(){
    for(int i=0;i<MAXT;i++)link[i].LP=c[i],link[i].id=i;
    S=&link[0];T=&link[MAXT-1];
    S->nxt=T;T->pre=S;
    LINK *pt=newpt();ins(S,T,pt);
}

题目大意

对一个 1\sim n 的排列实现如下操作：

将数字 p 的位置改为排列最前面。
将数字 p 的位置改为排列最后面。
将数字 p 的位置左移、右移或不动。
询问数字 p 的位置。
询问排列第 i 位的数字。

正文

看到 8\times 10^{4} 的数据范围，我就开始动歪脑筋了，显然这个范围是可以放 \mathcal{O}(n\cdot\sqrt{n}) 的复杂度的算法过的。

于是考虑块状链表维护插入和查询操作。具体地，我们先将上面提到的五个操作分解一下，以便我们思考：

操作 1，显然是让我们从排列中先删除一个数字，再把这个数字插入到排列最前面。

操作 2，是让我们从排列中先删除一个数字，再把这个数字插入到排列最后面。

操作 3，是让我们从排列中先删除一个数字，再把这个数字插入到排列中间一个位置。

操作 4，是让我们找到一个数字的位置。

操作 5，是让我们找到一个位置上的数字。

很显然，运用最最普通的块状链表的插入、删除和分裂操作，就可以维护操作 1、2、3、5 了。而操作 4 还需要我们开一个桶，记录下每个数字所在的块的编号，然后就可以对于每一个询问直接遍历所在的块找到数字的位置了。

具体地：

对于删除操作，先通过桶找到数字所在的块的编号，然后暴力遍历该块内的元素，遇到了该数字，就把后面的数字往前移，覆盖掉这个数字。

暴力遍历块内元素复杂度 \mathcal{O}(\sqrt{n})。

对于插入操作，我们先记录每个块的大小，然后从第一个块开始往后遍历，找到插入位置所对应的块，然后把块内在该位置之后的元素往后移一位，把数字放在该位置上。

暴力遍历块复杂度 \mathcal{O}(\sqrt{n})，暴力遍历块内元素复杂度 \mathcal{O}(\sqrt{n})，总复杂度 \mathcal{O}(\sqrt{n})。

注意：遍历块和遍历块内元素是两种操作。

到这里，我们已经可以实现操作 1~3 了。

对于查询数字的位置，先通过桶找到数字所在块的编号，然后从第一个块开始遍历块，知道遇见数字所在块，然后答案加上数字所在块之前所有块的大小之和；然后遍历所在块内元素，直到遇见该数字，然后答案加上该数字在块内的位置。最后输出答案，即为数字在排列中的位置。

暴力遍历块复杂度 \mathcal{O}(\sqrt{n})，暴力遍历块内元素复杂度 \mathcal{O}(\sqrt{n})，总复杂度 \mathcal{O}(\sqrt{n})。

对于查询位置对应的数字，就和插入操作一样，只不过把插入的步骤改为输出对应位置上的数字，复杂度和插入操作一样，都是 \mathcal{O}(\sqrt{n})。

于是到这里，我们已经可以实现操作 4~5 了。

于是到这里，我们已经可以实现所有的操作了。

单个操作复杂度 \mathcal{O}(\sqrt{n})，共 m 个操作，因此总时间复杂度 \mathcal{O}(m\cdot\sqrt{n})，可以通过本题。

需要注意的是，上述操作中，我默认大家都已经了解过了块状链表的原理，因此忽略了块状链表的分裂操作：具体的，当一个块的大小超过额定块长的两倍时，我们将这个块分成两个块，新块接在旧块之后，这样就可以保证数据不会大量堆积在同一个块内而影响效率了。

在插入操作中，需要调用分裂操作。

此外，这里再提醒一遍：不要忘记在插入和分裂操作之后，维护桶的信息。

接下来给出本题块状链表做法的代码：

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5,MAXT=1e3+514,MAXK=3e2+5;//数据范围、开数组的大小、额定块长
struct LINK{//链表结构体
    LINK *nxt,*pre;
    ll *LP,id;//LP 为该块存放信息的数组，id 为该块的编号
}link[MAXT*2];
ll tim,c[MAXT*2][MAXT*2],book[MAXN];
//tim 为块的数量，c 为 LP 指向的位置，book 为存放数字位置的桶
LINK *S,*T;//S 为链表的起点，T 为链表的终点
LINK *newpt(){return &link[++tim];}//分配一个新的块
void ins(LINK *x,LINK *y,LINK *t){//在两个块中间插入一个块
    x->nxt=y->pre=t;
    t->pre=x;t->nxt=y;
}//注意：该函数插入的是块，用来维护链表形态；下文的 ins_k 函数插入的是数字，用来维护链表的信息
void init(){//初始化
    for(int i=0;i<MAXT;i++)link[i].LP=c[i],link[i].id=i;//为所有待定的块分配数组和编号
    S=&link[0];T=&link[MAXT-1];//初始化起点和终点
    S->nxt=T;T->pre=S;//终点在起点之后，起点在终点之前
    LINK *pt=newpt();ins(S,T,pt);//最开始的一个块，在起点和终点之间
}
void split(LINK *t){//分裂操作
    if(t->LP[0]<=MAXK*2)return;//满足块长大于两倍额定块长才分裂
    LINK *pt=newpt();
    ins(t,t->nxt,pt);//新块插在旧块之后
    for(int i=MAXK+1;i<=t->LP[0];i++)book[pt->LP[++pt->LP[0]]=t->LP[i]]=pt->id;
    t->LP[0]=MAXK;//将旧块后半段信息转移给新块
}
void ins_k(ll id,ll k){//插入数字
    for(LINK *t=S->nxt;t!=T;t=t->nxt){
        if(k>t->LP[0])k-=t->LP[0];//如果插入的位置不在该块内
        else{
            for(int i=t->LP[0];i>=k+1;i--)t->LP[i+1]=t->LP[i];//插入位置之后的数字后移
            t->LP[k+1]=id;book[id]=t->id;t->LP[0]++;//插入数字
            split(t);//尝试分裂块
            break;
        }
    }
}
void ins_lst(ll id){//插入数字到最后一位
    LINK *pt=T->pre;//最后一位在最后一个块内
    pt->LP[++pt->LP[0]]=id;//最后一位在最后一个块的最后一位
    book[id]=pt->id;//别忘了维护桶！！！（大声）
    split(pt);
}
ll find_k(ll k){//寻找位置上的数字
    for(LINK *t=S->nxt;t!=T;t=t->nxt){
        if(k>t->LP[0])k-=t->LP[0];
        else return t->LP[k];
    }
    return -1;
}
void del(ll id){//删除数字
    bool flag=false;
    LINK *pt=&link[book[id]];//获得数字所在块
    for(int i=1;i<=pt->LP[0]-1;i++){
        if(pt->LP[i]==id)flag=true;//遇见了该数字
        if(flag)pt->LP[i]=pt->LP[i+1];//该数字之后的数字前移
    }
    pt->LP[0]--;//块大小减一
}
ll rank_(ll id){//查询数字的位置
    ll r=0;
    LINK *pt=&link[book[id]];
    for(LINK *t=S->nxt;t!=pt;t=t->nxt)r+=t->LP[0];
    for(int i=1;i<=pt->LP[0];i++){
        if(pt->LP[i]==id)break;
        r++;
    }
    return r;
}
void check(){//调试代码，不用管
    printf("Check : ");
    for(LINK *t=S->nxt;t!=T;t=t->nxt)
        for(int i=1;i<=t->LP[0];i++)printf("%lld ",t->LP[i]);
    printf("\n");
}
ll n,m,pi,ti;
char op[128];
int main(){
    init();
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&pi);
        ins_lst(pi);
    }
    while(m--){
        scanf("%s",op+1);
        if(op[1]=='T'){//操作一
            scanf("%lld",&pi);
            del(pi);ins_k(pi,0);
        }
        else if(op[1]=='B'){//操作二
            scanf("%lld",&pi);
            del(pi);ins_lst(pi);
        }
        else if(op[1]=='I'){//操作三
            scanf("%lld%lld",&pi,&ti);
            if(ti==0)continue;
            ll rk=rank_(pi);
            del(pi);
            if(rk+ti==n)ins_lst(pi);
            else ins_k(pi,rk+ti);
        }
        else if(op[1]=='A'){//操作四
            scanf("%lld",&pi);
            printf("%lld\n",rank_(pi));
        }
        else if(op[1]=='Q'){//操作五
            scanf("%lld",&pi);
            printf("%lld\n",find_k(pi));
        }
        // check();
    }
    return 0;
}

尾言

本片题解只是该题的块状链表做法，并不是块状链表教学，所以对于块状链表的操作和维护介绍得颇为粗略，还请见谅。

代码中有自认为详细的注释。

如有表述不清或错误的地方，请在评论区提出，感激不尽。

顺带一提，这种方法居然跑得比我的几个同学写的 fhq-Treap 和 splay 都要快些（乐）。

最后，祝大家看得开心！