← 返回题目列表

AtCoder · abc399_d

G. 开关座椅

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

N 情侣们坐成一排。
计算情侣的数量,使得两对情侣最初都没有坐在彼此旁边,并且通过在这四个人之间交换座位,两对情侣最终可以坐在彼此旁边。

有一个序列 A = (A_1, A_2, \dots, A_{2N}) 长度 2N。每个整数 1, 2, \dots, N 恰好出现两次 A.

查找整数对的数量 (a, b) 满意 1 \leq a < b \leq N 以及以下所有条件:

  • 两次出现 a in A 不相邻。
  • 两次出现 b in A 不相邻。
  • 通过以任意顺序执行一次或多次以下操作,可以达到以下状态: a in A 是相邻的并且两次出现 b in A 也相邻。
    • 选择一个整数对 (i, j) (1 \leq i \leq 2N, 1 \leq j \leq 2N) 这样 A_i = a 和 A_j = b,并交换 A_i 与 A_j.

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 每个 1, 2, \dots, N 恰好出现两次 A.
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
A_1 A_2 \dots A_{2N}

输出

打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

3
3
1 2 3 3 1 2
4
1 1 2 2 3 3 4 4
5
1 2 3 4 5 1 2 3 4 5

示例输出 1

1
0
4

考虑第一个测试用例。
(a, b) = (1, 2) 满足问题陈述中的条件,原因如下:

  • 两次出现 1 in A 不相邻。
  • 两次出现 2 in A 不相邻。
  • 通过执行以下操作 (i, j) = (1, 6) 并交换 A_1 与 A_6,您可以达到以下状态:两次出现 1 是相邻的并且两次出现 2 也相邻。

(1, 2) 是唯一的一对 (a, b) 满足条件。