题解 | #栈#（C++）

因为如题目所说我们要频繁进行入栈以及删除栈内部元素的操作，所以这边我们用一个链表来模拟栈，这样操作起来会更加方便，同时我们用一个哈希表来记录每个值对应的指针

每次插入元素前，先执行去重逻辑，如果之前栈中出现过，那么依次判断该元素和前后元素之和是否为奇数，如果是的话分别使答案-1（注意考虑边界），然后判断删除该元素后原本的前后元素之和是否为奇数，是的话让答案+1

然后去重完以后让元素入栈，入栈后判断他跟原本栈顶的元素（如果有的话）之和是否为奇数，是的话让答案+1

这题本身不难，实现上使用链表会方便很多 时间复杂度O(n)，能够满足条件

using namespace std;
#define endl '\n'
// #define int long long
// #define ctz __builtin_ctzll  // 不 define int long long记得删
// #define clz __builtin_clzll  // 不 define int long long记得删
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e6 + 10;
const ll MOD = 1e9 + 7; // 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;

void LiangBaiKai()
{
}

void Aiden()
{
    ll m, n, sum = 0, ans = 0, num = 0, i, j, k, mi = INF, ma = -INF, cnt = 0, x, y, len, t, l, r, cur;
    string s;
    cin >> n;
    list<ll> lst;  // 建立双向链表来模拟栈，栈底在链表头部，栈顶在链表尾部
    unordered_map<ll, list<ll>::iterator> pos;  // 值到链表迭代器的映射
    for (i = 1; i <= n; i++)
    {
        cin >> x;
        // 如果 x 已经存在，先删除旧节点（如果不存在，find的返回值是end）
        if (pos.find(x) != pos.end())
        {
            auto it = pos[x];
            auto pre_it = it;
            pre_it--;
            auto next_it = it;
            next_it++;
            // 判断先前的x跟它前一个数和是否为奇数
            if (it != lst.begin())
            {
                if ((*pre_it + x) & 1)
                    ans--;
            }
            // 判断先前的x跟它后一个数和是否为奇数
            if (next_it != lst.end())
            {
                if ((*next_it + x) & 1)
                    ans--;
            }
            // 判断删掉先前的x后前后的数和是否为奇数
            if (it != lst.begin() && next_it != lst.end())
            {
                if ((*pre_it + *next_it) & 1)
                    ans++;
            }
            // 消除链表中原来的x以及映射里的键x
            lst.erase(it);
            pos.erase(x);
        }
        // 把现在的x加入链表尾部（模拟入栈），获取新加入的x的迭代器位置
        bool flag = lst.empty();
        lst.push_back(x);
        auto new_it = lst.end();
        new_it--;
        // 当链表（模拟栈）非空的时候，判断新加入的x和原本栈顶的数的和是否为奇数
        if (!flag)
        {
            auto pr_it = new_it;
            pr_it--;
            if ((*pr_it + x) & 1)
                ans++;
        }
        // 更新映射和输出此时的答案
        pos[x] = new_it;
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //LiangBaiKai();
    int _ = 1;
    //cin >> _;
    while (_--)
        Aiden();
    return 0;
}

/*
                                                @@@@@@
                                                @   @@@@@@
                                                @ @  @@  @@@@
                                               @@ @@@    @@@@@
                                               @  @@@@@@@@
                                              @@@@
                                              @
                                  @@@@@@@@@@ @@ @@@@@@@@@@@@
                              @@@@@          @              @@@@@
                          @@@                @                   @@@
                       @@@                  @@                      @@@
                     @@                                                @@@
                   @@                                                     @@
                 @@                                                        @@
                @@                                                           @@
               @                                                              @@
              @          @@@@@@@@                                              @@
             @     @@@  @@@@@@@@@                                               @
            @@  @@@@@@@ @@@@@@@@  @@@@@@                                         @
            @  @@@@@@@@@@@@@@@@@@@@@@@@@@                                        @@
            @ @@@@@@@@@@@      @@@@@@@@@@@                                        @
             @@@@@@@@@@@@@   @@@@@@@@@@@@@@  @                             @@@@@@ @
            @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    @@      @@@@@@         @@@        @
           @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@      @@@         @@@  @@@          @
          @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                                  @@@@@
         @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     @@@
        @@@@@@       @@@@@@@@@@  @@@@@@@@@@@@@@                                        @@
       @@@@@  @@@@@@@ @@@@@@   @@   @@@@@@@@@@@                                     @@@
       @@@@@ @@@@@@@@  @@@@  @@@@@@@ @@@@@@@@@@@                                 @@
      @@@@@@  @@@@@@@ @@@@@  @@@@@@@  @@@@@@@@@@@@                            @@@@@@@
      @@@@@@@    @   @@@@@@  @@@@@@@ @@@@@@@@@@@@@@@@                      @@@@@@@@@@@
      @@@@@@@@@@@@@@@@@@@@@@@   @   @@@@@@@@@@@@@@@@@@@                @@@@@@@@@@@@@@@@@
      @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@          @@@@@@@@@@@@@@@@@@@@@
      @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@   @@@@@@@@@@@@@ @@@@@@@@@@
       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@              @@@@@@@@@@
       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               @       @   @  @@@@@@@@@@@@
       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@        @ @@@@@ @        @@@@   @   @@@@@@@@@@
        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    @@      @@      @@    @@@   @@@@@   @@@@@@@@@@
         @@@@@@@        @@@@@@@@@@@@@@         @@@@@@         @@@@@              @ @@@@@@@@
          @@@@@@        @@@@@@@@@@@                                             @  @@@@@@@@
           @@@@         @@@@@@@@                                              @@  @@@@@@@
              @@                                                              @@    @@@@@
               @@@                                                          @@
                  @@@                                                    @@@
                     @@@@@@@@@@@@                            @@@@@@@@@@@
                                @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/