AT_abc421_f 题解

· · 题解

管这叫 F？这边建议将这个 F 放到 D 的位置上去，原 D 就放到 F 上吧，别早早的就把人恶心了。

大概就是让你维护一个链表，支持两种操作，一种操作是在某个数值后面插入某个值，还有一种操作就是计算两个数值（不保证先后顺序）之间（不包含这两个数值）的所有数字之和，并将这中间的所有数字都从链表中删去。

肯定是维护双向链表。

第一种操作很简单，只需要额外开个 live 数组记录下每个数值所处位置的 cnt 编号。存点的时候记一下即可，特别简单。

第二种操作则复杂些。如果不考虑时间复杂度的话，那直接暴力跑就成。从 x 出发，往左边跑，看能不能碰上 y——如果碰上，那就累加中间数值的和并删掉它们；如果碰不上，那就往右走，因为题目保证了 y 肯定存在，所以不在左边那就是在右边了。

但是如果题目刻意构造数据去卡，这种解法是会 TLE 的，最坏能卡到平方级别。因此考虑优化。

要是能够快速得知 x 和 y 在链表中的方向关系（即谁在左谁在右）就好了，那样时间复杂度就是 O(n) 了。但是这题远不用这么复杂。只要你运气好，上面那种暴力解法是可以过的，也就是说，在 x 左边和右边两个方向中，一条是死胡同，还有一条是正确道路。那么就有一个很巧妙的想法，也就是同时跑。

具体来说，就是开两个指针 i 和 j，i 顺着 x 往左边跑，而 j 顺着 x 往右边跑。如果其中一个碰到了 y 值，那么倒回来计算一下和（其实上在中途遍历的时候算也是可以的哈，但是常数不是问题所以我就图方便了），删点，然后 break 掉循环就好。当然，如果其中一个到了顶（链表的最左端或者最右端）还没找到 y，那么显然答案就是在另一边了，这个时候如果另一边还没找到，就一直继续探，因为 y 也只有可能在这边了。

这样的话，时间复杂度也还是 O(n) 级别的，常数大些而已。

注意还没有执行任何操作的时候有一个值为 0 的节点在链表里，初始化的时候记得把它放上。

代码特别简略。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 5e5+5;
struct line{LL x,pre,nxt;}a[N];
LL Q,live[N],cnt;
LL min(LL x,LL y){return (x<y?x:y);}
LL max(LL x,LL y){return (x>y?x:y);}
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    Q=read();a[++cnt]={0,0,0},live[0]=1;
    for(LL H=1;H<=Q;H++){
        int opt=read();
        if(opt==1){
            int x=read(),p=live[x];
            a[++cnt]={H,p,a[p].nxt};live[H]=cnt;
            a[a[p].nxt].pre=cnt,a[p].nxt=cnt;
        }else{
            int x=read(),y=read(),p=live[x];LL sum=0;
            for(int i=p,j=p;i&&j;i=a[i].pre,j=a[j].nxt)
                if(a[i].x==y||(!a[j].nxt&&a[j].x!=y)){
                    int k=a[p].pre;
                    for(;a[k].x!=y;k=a[k].pre)sum+=a[k].x;
                    a[k].nxt=p,a[p].pre=k;break;
                }else if(a[j].x==y||!a[i].pre){
                    int k=a[p].nxt;
                    for(;a[k].x!=y;k=a[k].nxt)sum+=a[k].x;
                    a[p].nxt=k,a[k].pre=p;break;
                }else;cout<<sum<<"\n";
        }
    }
    return 0;
}

AC 记录。

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！