题解：P12288 [蓝桥杯 2024 国 Java A] 栈

fish_love_cat · 2025-10-27 23:49:08 · 题解

要求写一个数据结构，支持单点删除，末尾增加，快速求前后数字。

考虑双向链表。

我们对于每个数字统计前后数字，删除的时候改一次贡献，增加的时候再改一次贡献就做完了。

正常链表写法就可以，由于第一次插入不需要删除，所以还要记录一个 vis 数组。

不要忘记二次插入某个数字时清空删除前的维护信息。

#include<bits/stdc++.h>
using namespace std;
struct fish{
    int pre,nxt;
    bool vis;
}a[1000005];
int lst=-1,ans;
int main(){
    int n,x;
    cin>>n>>x,n--;
    a[x].pre=a[x].nxt=-1;
    a[x].vis=1;
    lst=x;
    puts("0");
    while(n--){
        cin>>x;
        if(a[x].vis){
            if(a[x].pre!=-1)
            ans-=(x+a[x].pre)&1;
            if(a[x].nxt!=-1)
            ans-=(x+a[x].nxt)&1;
            if(a[x].pre!=-1&&a[x].nxt!=-1)
            ans+=(a[x].pre+a[x].nxt)&1;
            if(a[x].pre!=-1)
            a[a[x].pre].nxt=a[x].nxt;
            if(a[x].nxt!=-1)
            a[a[x].nxt].pre=a[x].pre;
            if(a[x].nxt==-1)lst=a[x].pre;
        }
        a[x].pre=lst;
        a[x].vis=1;
        a[x].nxt=a[lst].nxt;
        if(lst!=-1)
        a[lst].nxt=x,ans+=(lst+x)&1;
        lst=x;
        cout<<ans<<'\n';
    }
    return 0;
}
//「是啊。虽然不清楚，但我大概回应不了你的期待。我一直都是这样。无论是谁的期望，我都回应不了。」