【栈 / 链表板子题】

 题目

代码

#include <bits/stdc++.h>
using namespace std;struct N
{int v;N* p;N* n;N(int x) : v(x), p(0), n(0) {}
};
int main()
{int m;cin >> m;N* h = 0;N* t = 0;int c = 0;unordered_map<int, N*> mp;for(int i = 1; i <= m; i++){int x;cin >> x;if(mp.count(x)){N* d = mp[x];if(d->n)if((d->n->v + d->v) % 2)c--;if(d->p){if((d->p->v + d->v) % 2)c--;if(d->n)if((d->p->v + d->n->v) % 2)c++;}if(d->n)d->n->p = d->p;elset = d->p;if(d->p)d->p->n = d->n;elseh = d->n;mp.erase(x);delete d;}N* nn = new N(x);if(!t)h = t = nn;else{if((t->v + nn->v) % 2)c++;t->n = nn;nn->p = t;t = nn;}mp[x] = nn;cout << c << '\n';}while(h){N* tmp = h;h = h->n;delete tmp;}return 0;
}