自动搬运

查看原文

来自洛谷，原作者为

	liborui0000 这个家伙很懒，什么也没有留下（只是懒得写罢了）

搬运于2025-08-24 23:14:22，当前版本为作者最后更新于2025-06-19 21:49:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12288 题解

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

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

1. $j$ 是链表第一个元素，那么它只对后面的 $ans$ 有贡献，所以将它对后面的贡献减去。
2. $j$ 是链表当前的最后一个元素，那么它只对前面的 $ans$ 有贡献，所以将它对后面的贡献减去。
3. $j$ 是链表中间的元素，那么它对前面和后面的 $ans$ 都有贡献，所以都减去。如果被删除后 $j$ 前面和后面的两个数和是奇数，那么 $ans$ 应加 $1$ 。

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

于是我们就快乐的通过了这道题 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;
}