#P14222. [2026队测系列]星港远征计划之被盗的项链

[2026队测系列]星港远征计划之被盗的项链

题目背景

星港远征计划中,远征队从遗迹中取回了 2N2N 枚能量宝石。每种型号的宝石恰好有两枚,但在运输途中被打乱成一排。
为了进行后续分析,你希望在这排宝石之间插入若干隔板,把它们分成若干连续区间。要求把从左往右编号为奇数的区间中的宝石全部收集起来后,能够恰好得到每种型号各一枚。
请你构造一种满足条件的分隔方案。

题目描述

2N2N 个宝石从左到右排成一列,第 ii 个宝石的种类为 AiA_i。其中,AiA_i11NN 之间的整数,并且每一种类型的宝石都恰好出现两次

你需要插入若干隔板,使其满足以下条件:

  • 每个隔板的位置用一个整数 ii1i2N11 \le i \le 2N-1)表示,表示在从左起第 ii 个宝石与第 i+1i+1 个宝石之间插入隔板;
  • 同一个位置不能插入两个或以上的隔板;
  • 隔板总数 KK 不超过 NN
  • 插入这 KK 个隔板后,整列宝石会被分成 K+1K+1 个连续区间。此时,将从左往右编号为奇数的区间中的全部宝石取出,要求恰好得到种类 1,2,,N1,2,\ldots,N 的宝石各一枚。

请输出任意一种满足条件的插入方法。可以证明,这样的方法一定存在。

共有 TT 组测试数据,你需要分别求解。

输入格式

输入从标准输入给出,格式如下:

T
case1
case2
...
caseT

每组测试数据的格式为:

N
A1 A2 ... A2N

输出格式

按顺序输出 TT 组测试数据的答案。

对于每组测试数据,设隔板数量为 KK,隔板位置按升序为 C1,C2,,CKC_1,C_2,\ldots,C_K,则输出格式为:

K
C1 C2 ... CK

其中必须满足 KNK \le N

样例 #1

输入

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

输出

3
1 2 4
1
5

说明

对于第 11 组测试数据,在位置 1,2,41,2,4 插入隔板后,宝石会被分成:

  • (1)(1)
  • (2)(2)
  • (2,3)(2,3)
  • (3,1)(3,1)

取出从左往右编号为奇数的区间中的全部宝石后,可得到种类 1,2,31,2,3 各恰好一枚。

数据范围

  • 1T1051 \le T \le 10^5
  • 1N2×1051 \le N \le 2 \times 10^5
  • 1AiN (1i2N)1 \le A_i \le N \ (1 \le i \le 2N)
  • 对于每个 x (1xN)x \ (1 \le x \le N),满足 Ai=xA_i=x 的位置恰好有两个
  • 所有测试数据中 NN 的总和不超过 2×1052 \times 10^5
  • 输入中的所有值均为整数