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

liborui0000 · 2025-06-19 21:49:43 · 题解

P12288 题解

核心：双向链表维护栈内数据，用 map 维护每个数出现的次数和位置（因为 map 内元素键的数量是唯一的便），于查找和删除。

我们可以用一条双向链表储存每个数据的前驱和后继。用 ans 代表栈内相邻元素和是奇数的组数。每次向链表里添加元素时，先判断在 map 里有无重复元素（j）。如果有，分三种情况：

判断完成后将新元素添加到链表中，并计算新元素对答案的贡献。最后输出。

于是我们就快乐的通过了这道题 QAQ。

AC code：

#include <bits/stdc++.h>

using namespace std;
#define int long long

int n;
const int N = 5e5 + 10;
const int M = 1e6 + 10;

struct node{
    int prev, nxt, id;
}a[N];

map<int, int> num;
int ans = 0, cnt = 2;

inline void add(int k, int x){
    a[cnt].id = x;
    a[cnt].nxt = a[k].nxt;
    a[a[k].nxt].prev = cnt;
    a[cnt].prev = k;
    a[k].nxt = cnt;
    cnt++;
}

signed main(){
    cin >> n;
    a[0].nxt = 1;
    a[1].prev = 0;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        int j = 0;
        if (num[x]){
            j = num[x];
            int pre = a[j].prev;
            int next = a[j].nxt;
            if (pre) ans -= (a[pre].id + a[j].id) % 2;
            if (next != 1) ans -= (a[next].id + a[j].id) % 2;
            if (next != 1 && pre != 0) ans += (a[next].id + a[pre].id) % 2;
            a[a[j].prev].nxt = a[j].nxt;
            a[a[j].nxt].prev = a[j].prev;
        }
        num[x] = i + 1;
        add(a[1].prev, x);
        j = num[x];
        if (a[j].prev) ans += (a[j].id + a[a[j].prev].id) % 2;
        cout << ans << "\n";
    }
    return 0;
}