[ ARC215B ] Stolen Necklace
link.
好巧妙的构造！！！（？
很简单，但并没有想到...
我们采取以下的构造策略：
从左向有扫一遍。
若\(a_i\)第一次出现，不用管它，继续向前扫；
否则检查当前分到的组的奇偶性与前一个\(a_i\)出现的位置的奇偶性是否相同。
如果相同，那么需要将这个元素新单开一组；
否则不必管它。
由于保证每个\(a_i\)的两个位置所处分组的奇偶性均不相同，所以一定每一个元素均可以取到。
同时单开一组这个操作至多只会进行\(n\)次，满足题目要求。
时间复杂度：\(O(n)\).
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf 1e10
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=4e5+5;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,a[N];
bool vis[N],pos[N];
vector<int>ans;
signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int T; cin>>T;while(T--){cin>>n;for(int i=1;i<=2*n;i++) cin>>a[i];bool op=1;for(int i=1;i<=2*n;i++){if(!vis[a[i]]){vis[a[i]]=1;pos[a[i]]=op;continue;}if(op==pos[a[i]]){op^=1;ans.push_back(i-1);}}cout<<ans.size()<<'\n';for(auto u : ans) cout<<u<<' ';cout<<'\n';for(int i=1;i<=n;i++) pos[i]=vis[i]=0;ans.clear();}return 0;
}