AT_abc225_d 题解

· · 题解

题目传送门

更好的阅读体验

Part0：前言

楼上 + 同班同学 YangXiaopei 已经写得很详细了，但是我觉得还是有些部分讲的比较粗糙，所以写了这篇题解。

Part1：前置知识

这道题我们需要用的是链表，下面简单介绍一下链表是什么。

链表是一种非连续的数据结构，元素的顺序是通过链表中的指针次序实现的。不同于数组，链表是不能通过下标查询的。对于链表中的每一个元素 i，他们都有自己的前一项 l_i 以及 后一项 r_i。那么，我们如何表示元素 a 在元素 b 的前面呢？

void link(int a,int b){
    r[a]=b;
    l[b]=a;
}

而第 1 项没有前一项，于是我们可以给他加一个，记为 HEAD，类似地，最后一项的下一项我们记为 END。

于是，我们用一个链状的数据结构记录下了每个元素。

那有人就问了：数组是用 for 循环通过下标遍历的，那链表没有下标，如何遍历呢？其实很简单。

for(int i=r[HEAD];i!=END;i=r[i])

解释一下：我们从 HEAD 的后一项开始遍历，遍历到 END 时结束， i 每次变到原来的下一项。

知道这些基本知识后，我们来看一下链表和数组的对比。如下表：

链表 数组 链表时复 数组时复
在 A 和 B 之间插入 C A 的下一项变成 C，B 的上一项变成 C B 及其以后的元素集体往右挪一个位置，B 原来的位置让给 C O(1) O(n)
删除 A 这个元素 将 A 的前一项与后一项联系起来 A 的后面所有元素往左挪一个位置 O(1) O(n)
知道元素找位置 从头到尾遍历+判断 下标查询 O(n) O(1)
知道位置找元素 从头到尾遍历+记录个数 下标查询 O(n) O(1)

可以观察到，链表做插入和删除操作的效率很高。

Part2：题目大意

三种操作：

Part3：题目分析

无论是第一种连接操作还是第二种删除操作，链表都可以用 O(1) 的时间复杂度完成。所以，我们愉快地选择用链表解决此题。

Part4：代码实现

  1. 预处理：通常情况下，我们只需要在一条链上进行操作，但这次不同，我们并不知道会出现多少条链，链的个数最大的情况可达到 n 个。所以，我们可以刚开始把每个元素都当成一条链进行操作。
for(int i=1;i<=n;i++){
    link(HEAD,i);
    link(i,END);
}
  1. 连接操作：用上文所讲的 link 函数连接 x 和 y 即可。
void opera1(){
    int x,y;
    cin>>x>>y;
    link(x,y);
}
  1. 删除操作：删除 x 和 y 的联系，把一条链在 x 和 y 连接的地方断开。因此原来的 1 条链会变成 2 条，而且第 1 条的结尾是 x，第 2 条的开头是 y。那把 x 和 END，y 和 HEAD 连接不就行了！
void opera2(){
    int x,y;
    cin>>x>>y;
    link(x,END);
    link(HEAD,y);
}
  1. 查询操作：纯模拟。先往左右各扫一遍，记录链的长度，然后输出。接着再扫一遍，扫到左端点，一直往右遍历，再不停输出遍历到的点即可。可能有点不太清楚，看代码吧。
void opera3(){
    int x;
    cin>>x;
    cnt=1;//刚开始是一，因为无论扫左边还是扫右边都不会扫到x，所以x要被提前记录
    pos=x;
    while(l[pos]!=HEAD){//扫左
        pos=l[pos];
        cnt++;
    }
    pos=x;
    while(r[pos]!=END){//扫右
        pos=r[pos];
        cnt++;
    }
    cout<<cnt<<" ";//输出元素个数
    pos=x;
    while(l[pos]!=HEAD)//再扫左
        pos=l[pos];
    while(1){//一直往右，直到扫到的元素的下一项是END
        cout<<pos<<" ";
        if(r[pos]==END)
            break;
        pos=r[pos];
    }
    cout<<"\n";
}

Part5：最后代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,cnt,pos;
int l[N],r[N];
const int HEAD=0;
const int END=1e5+1;//注意END的取值，一般是比n多一点点，这样可以保证不被扫到
void link(int a,int b){
    r[a]=b;
    l[b]=a;
}
void opera1(){
    int x,y;
    cin>>x>>y;
    link(x,y);
}
void opera2(){
    int x,y;
    cin>>x>>y;
    link(x,END);
    link(HEAD,y);
}
void opera3(){
    int x;
    cin>>x;
    cnt=1;//刚开始是一，因为无论扫左边还是扫右边都不会扫到x，所以x要被提前记录
    pos=x;
    while(l[pos]!=HEAD){//扫左
        pos=l[pos];
        cnt++;
    }
    pos=x;
    while(r[pos]!=END){//扫右
        pos=r[pos];
        cnt++;
    }
    cout<<cnt<<" ";//输出元素个数
    pos=x;
    while(l[pos]!=HEAD)//再扫左
        pos=l[pos];
    while(1){//一直往右，直到扫到的元素的下一项是END
        cout<<pos<<" ";
        if(r[pos]==END)
            break;
        pos=r[pos];
    }
    cout<<"\n";
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        link(HEAD,i);
        link(i,END);
    }
    while(q--){
        int opt;
        cin>>opt;
        if(opt==1)
            opera1();
        if(opt==2)
            opera2();
        if(opt==3)
            opera3();
    }
    return 0;
}