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

· · 题解

本人看了其他题解（没有细看），感觉有点复杂，可能也是我没看懂吧。

SOLUTION

这题的思路其实并不复杂，只要有一些数据结构基础的，可以看出来，这题其实是一道链表题，并非题面中所说的栈。那么很简单了。

注意到 1 \le A_i \le 10^6，完全可以使用一个数 f_i，记录 i 有没有出现过，出现过我们进行处理，如果需要删除的这个 A_i 与左边元素相加为奇数，答案减一，右边同理，但如果左边元素和右边元素相加也为奇数，答案加一，到这很容易理解吧？

然后下面的处理就简单很多，直接把 A_i 添加至末尾，如果与左边的数相加为奇数，答案加一。

这里有一个细节，如果左边或右边的数到达边界（或称为不存在），则不能判相加是否为奇数，我定义了左边界和右边界变量，因为没有处理边界，导致 WA 掉了。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5 , HEAD = 1e6 + 1 , END = 1e6 + 2;//HEAD、END分别为左边界和右边界
int n , a , L[N] , R[N] , now;
bool f[N];
//链表处理函数
void link(int x , int y){
    R[x] = y;
    L[y] = x;
}
void ins_l(int x , int y){//本题无用可删
    link(L[y] , x);
    link(x , y);
}
void ins_r(int x , int y){
    link(x , R[y]);
    link(y , x);
}
void del(int x){
    link(L[x] , R[x]);
}
signed main(){
    cin >> n;
    link(HEAD , END);
    while(n--){
        cin >> a;
        if(f[a]){//出现过的处理
            if(((L[a] + a) & 1) && L[a] != HEAD)now--;
            if(((R[a] + a) & 1) && R[a] != END)now--;
            if(((L[a] + R[a]) & 1) && L[a] != HEAD && R[a] != END)now++;
            del(a);
        }
        f[a] = true;
        ins_l(a , END);
        if(L[a] != HEAD && ((L[a] + a) & 1))now++;
        cout << now << '\n';
    }
    return 0;
}