构造模拟题，思路很简洁，但是代码不好写。
首先看到数据范围，发现 \(k\) 的数据范围很特殊，种类少一种就是部分分，所以 \(k\) 一定是关键的，先思考 \(k=2n-2\) 的情况。
\(k=2n-2\)
观察两种操作，对于即将进入的牌 \(x\)，若某个栈顶或栈底有相同的 \(x\)，我们都可以很快的将其消去。这启发我们：
- 把所有栈的数量控制在 \(2\) 以内是最优的，并且所有相同类型的牌不会在栈中出现第二次。
- 当某类牌出现偶数次时，会被消光。
再回到数据范围，如果我们将 \(2n-2\) 种牌放到前 \(n-1\) 个栈中，由于一定有空栈，我们就可以任意消去所有类型的牌，不会无解。
\(k=2n-1\)
我们仍然想要沿用之前的思路，但是会遇到新的情况，即前 \(n-1\) 个栈都放满了，而即将放入的栈是第 \(2n-1\) 种牌 \(x\)。此时如果放入空栈，容易导致无解。
这时我们考虑什么时候不能放在空栈。发现如果放在空栈，当遇到一个目前类型在栈底的牌，并且此时它仍被栈顶挡住时，就无解了；如果两张 \(x\) 之间没有在栈底的牌，这时我们可以放入栈底。而我们可以枚举找到第一个在类型在栈底的牌 \(y\)，所在的栈为 \(s\)，这时再考虑什么情况它仍会被栈顶挡住。
设栈 \(s\) 的栈顶为 \(p\)：
如果 \(x\) 到 \(y\) 中的 \(p\) 数量为偶数时，把 \(x\) 放在 \(s\) 上，把所有 \(p\) 都放入空栈消掉，最后用空栈删去 \(y\)。
如果 \(x\) 到 \(y\) 中的 \(p\) 数量为奇数时，把 \(x\) 放在空栈，这是我们可以把 \(p\) 全放入 \(s\) 中把栈顶消去，最后把 \(y\) 放入 \(x\) 中，此时发现 \(s\) 栈空了，而原本的空栈多了一个 \(x\)，也就是空栈变成了 \(s\)。
现在思路就清晰了：
能用先前的思路就用先前的思路，不能用就分类讨论。
代码能力在这里就体现了，如果没有运用合适的数据结构就会写的很复杂。
- 对于可用的位置我们用队列维护，原先每个栈放两个位置进去。
- 对于栈，我们用双端队列维护，我们还需要每个种类的牌此时所在的位置，用数组 \(id\) 记录。
- 对于答案记录，边模拟边记录，数组或 vector 都可以。
- 由于操作会多次调用，所以考虑用函数封装，使主函数代码更简洁。
每一次枚举找到第一个在类型在栈底的牌后，我们可以直接将 \(i=r\)，复杂度是 \(O(m)\)。
总结：一题有思维的模拟题，需要从数据范围出发，找到启发性性质，对模拟过程有清晰思路后才开始写代码；用合适的数据结构维护数据和模拟过程。
#include <bits/stdc++.h>
typedef std::pair<int, int> pii;
typedef long long ll;
int read() {
int x = 0, f = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) {
x = (x << 3) + (x << 1) + (c - '0');
c = getchar();
}
return x * f;
}
int t, n, m, k, sp;
int a[2000010], id[610];
std::deque<int> st[610];
std::vector<pii> ans;
std::queue<int> q;
void pu(int x) {
ans.push_back({0, x});
}
void del(int x, int y) {
ans.push_back({x, y});
}
bool normal(int a) {
int s = id[a];
if(!s) {
if(q.empty()) return 0;
s = q.front();
q.pop();
pu(s);
st[s].push_back(a);
id[a] = s;
}
else {
id[a] = 0;
q.push(s);
if(st[s].back() == a) {
pu(s);
st[s].pop_back();
}
else {
pu(sp);
del(s, sp);
st[s].pop_front();
}
}
return 1;
}
void Solve() {
memset(id, 0, sizeof(id));
while(!q.empty()) q.pop();
ans.clear();
n = read(), m = read(), k = read();
sp = n;
for(int i = 1; i <= m; i++) a[i] = read();
for(int i = 1; i < n; i++) {
q.push(i), q.push(i);
}
for(int i = 1; i <= m; i++) {
if(!normal(a[i])) {
int r = i + 1, x = a[r], now = a[i];
for(; r <= m && x != now && st[id[x]].back() == x; r++, x = a[r]);
if(x == now) {
pu(sp);
for(int l = i + 1; l < r; l++) {
normal(a[l]);
}
pu(sp);
}
else {
bool flg = 0;
int s = id[x], y = st[s].back();
for(int l = i + 1; l < r; l++) {
if(a[l] == y) {
flg ^= 1;
}
}
if(!flg) {
pu(s);
st[s].push_back(now);
for(int l = i + 1; l < r; l++) {
if(a[l] == y) pu(sp);
else normal(a[l]);
}
pu(sp);
del(s, sp);
st[s].pop_front();
id[x] = 0;
id[now] = s;
}
else {
pu(sp);
st[sp].push_back(now);
for(int l = i + 1; l < r; l++) {
if(a[l] == y) pu(s);
else normal(a[l]);
}
pu(s);
id[x] = id[y] = 0;
id[now] = sp;
st[s].clear();
q.push(sp);
sp = s;
}
}
i = r;
}
}
std::cout << ans.size() << "\n";
for(pii p : ans) {
if(p.first == 0) std::cout << "1 " << p.second << "\n";
else std::cout << "2 " << p.first << " " << p.second << "\n";
}
}
int main() {
t = read();
while(t--) Solve();
return 0;
}