题解：AT_abc399_d [ABC399D] Switch Seats
xhxxwcr
·
·
题解
题意
请统计满足以下所有条件的 **两对不同的情侣对** $(a, b)$ 的组数：
1. 在原序列中，$a$ 的两个出现位置不邻接。
2. 在原序列中，$b$ 的两个出现位置不邻接。
3. 通过执行以下操作（次数不限），可以使 $a$ 的两个出现位置邻接，同时 $b$ 的两个出现位置也邻接：
- 选择两个位置 $(i, j)$ 满足 $A_i = a$ 且 $A_j = b$，并交换这两个位置的值。
给定一个长度为 $2N$ 的序列 $A = (A_1, A_2, \dots, A_{2N})$，其中每个 $1, 2, \dots, N$ 恰好出现两次。
对于 $T$ 个测试用例，分别输出答案。
~~我是天才。~~
好了，不整了。
下面是正片：
求存在多少个数对 $(a,b)$ 满足上述条件。
~~我是天才。~~
## 思路
对于每一个 $a_i(2\le i \le 2n)$ ，判断:
1. 是否在之前出现过
- 使用数组记录最后一个数并判断
2. 是否连续
3. 前一个或后一个是否是下一次出现的前一个或后一个
## 代码
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000010];
int lst[1000010];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
cin >> a[i];
lst[a[i]] = i;
}
a[2 * n + 1] = 0;
int ans = 0;
for (int i = 2; i <= 2 * n; i++) {
if(lst[a[i]] <= i + 1) continue;
if(a[lst[a[i]] + 1] == a[i + 1] || a[lst[a[i]] - 1] == a[i - 1]) ans ++;
}
cout << ans << "\n";
}
signed main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
```