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

· · 题解

由于需要支持在添加已有数字时将原有的该数字删除（可以视为将栈中某个元素移到栈顶，即先删去该元素，再将其插入至栈顶），但数据范围不大（1\le A_i\le10^6），而且要维护当前栈内相邻的数中和为奇数的组数，故我们可以考虑使用双向链表模拟该栈，并用 idx_i 记录当前值为 i 的数据在其中的下标（若不存在则为 -1）。

同时，我们可以维护一个 ans 变量，记录当前栈内相邻的数中和为奇数的组数。在栈顶（即链表的开头）插入一个数据时，如果当前栈中已有数据（即链表的开头位置不为 0），则检查栈顶数据和新插入的数据之和是否为奇数，如果是，则将 ans 加 1。删除某个数据时，如果该数据存在前驱，则要判断其前驱与其之和是否为奇数，如果是，则将 ans 减 1；对后继的判断同理（满足条件时也是将 ans 减 1）；此外，如果其同时拥有前驱和后继，则还要判断其前驱、后继之和是否为奇数，如果是，则将 ans 加 1。

据此，我们可以在 O(1) 的时间复杂度内完成一次操作，总时间复杂度 O(n)，可以通过本题。

Code：

import java.util.Scanner;
public class Main {
    static final int M = 500005, V = 1000005;   // 查询数, 值域
    public static class dataList {  // 使用双向链表实现的数据列表 (用于维护题目所述的栈)
        int[] q = new int[M], pre = new int[M], nxt = new int[M], idx = new int[V];
        // 存放的值, 每个位置的前驱, 每个位置的后继, 每个值对应的下标 (不存在则为 -1)
        int head, tail, tot, ans;
        // 开头下标, 结尾下标, 当前用到的下标的最大值, 当前相邻的数中和为奇数的组数
        public dataList() {    // 构造函数
            for(int i = 0; i < M; i++) {
                this.q[i] = this.pre[i] = this.nxt[i] = 0;
            }
            for(int i = 0; i < V; i++) {
                this.idx[i] = -1;
            }
            this.head = this.tail = this.tot = this.ans = 0;
        }
        public void insert(int x) { // 将 x 插入到首部
            this.q[++this.tot] = x;
            this.idx[x] = this.tot;
            this.pre[this.tot] = 0;
            this.nxt[this.tot] = this.head;
            if(this.head != 0) {
                if((this.q[this.head] + this.q[this.tot]) % 2 == 1) {   // 维护答案
                    this.ans++;
                }
                this.pre[this.head] = this.tot;
            }
            this.head = this.tot;
            if(this.tail == 0) {
                this.tail = this.tot;
            }
        }
        public void erase(int x) {  // 删除值为 x 的元素
            if(this.idx[x] == -1) {
                return;
            }
            int i = this.idx[x];
            this.idx[x] = -1;
            if(this.pre[i] != 0) {
                if((this.q[this.pre[i]] + this.q[i]) % 2 == 1) {    // 维护答案
                    this.ans--;
                }
                this.nxt[this.pre[i]] = this.nxt[i];
            } else {
                this.head = this.nxt[i];
            }
            if(this.nxt[i] != 0) {
                if((this.q[this.nxt[i]] + this.q[i]) % 2 == 1) {    // 维护答案
                    this.ans--;
                }
                this.pre[this.nxt[i]] = this.pre[i];
            } else {
                this.tail = this.pre[i];
            }
            if(this.pre[i] != 0 && this.nxt[i] != 0) {
                if((this.q[this.pre[i]] + this.q[this.nxt[i]]) % 2 == 1) {  // 维护答案
                    this.ans++;
                }
            }
        }
        /*
        public void print() {   // 打印队列, 调试用
            for(int i = this.head; i != 0; i = this.nxt[i]) {
                System.out.print(this.q[i] + " ");
            }
            System.out.println();
        }
        */
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        dataList Q = new dataList();
        int n = sc.nextInt();
        for(int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            Q.erase(x); // erase 函数中会判断当前 x 是否在 dataList 中, 故此处无需判断 
            Q.insert(x);
            System.out.println(Q.ans);
        }
        sc.close();
    }
}