补一下往年的构造题。。。
\(k\) 大概是 \(n\) 的两倍往下，这启示我们每个栈最多只放两个元素。
首先考虑 \(k=2n-2\) 的分，容易得到一个策略：留一个空栈不放，每个栈最多放两个。如果当前卡牌存在一个栈顶/栈底和它一样，那当前牌总是可以消掉的。否则当前栈中的卡牌一定两两不同，那一定还留有一个空位置没有放牌。
然后是 \(k=2n-1\)，我们仍然用一样的策略，不同的是牌数恰好比位置多 \(1\)，存在栈中放满了但是不能消掉的情况。设栈顶的牌种类集合为 \(S\)，我们在牌堆中从上到下找到第一个不在 \(S\) 中的牌 \(u\)，如果 \(u\) 是当前要放的牌，那就可以把当前放到空栈里，中间的牌一定能不用空栈消掉，放完之后再消掉空栈里的 \(u\) 即可。
否则 \(u\) 一定在某个栈的栈底出现过，我们记这个栈栈顶的元素为 \(v\)，统计从当前要放的牌一直到 \(u\) 中 \(v\) 出现了多少次。如果出现了奇数次，那可以当前牌放空栈，剩下的牌该怎么放怎么放，放到 \(u\) 之后原本 \(u\) 这一列会变成新的空栈。否则将当前牌放到 \(u\) 为栈底这一列的顶端，然后剩下的牌该怎么放怎么放，一定能全消完，直到 \(u\) 的时候将 \(u\) 放进空栈，然后就可以消掉底部的 \(u\)，此时空栈还是空栈，\(u\) 这一列也只会剩下两个元素。不断重复这个过程就可以构造出方案了。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int T, n, m, k;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
int c[N];
deque<int> q[305];
set<int> emp;
vector<pair<int, pair<int, int >>> res;
set<int> S;
int tp[N], bt[N];
inline void remove(int x) {
if (q[x].empty()) emp.erase(x);
else { emp.insert(x); tp[q[x].back()] = 0; bt[q[x].front()] = 0; }
if (q[x].size() < 2) S.erase(x);
else S.insert(x);
}
inline void add(int x) {
if (q[x].empty()) emp.insert(x);
else { emp.erase(x); tp[q[x].back()] = x; bt[q[x].front()] = x; }
if (q[x].size() < 2) S.insert(x);
else S.erase(x);
}
inline void print() {
cerr << "PRINT : " << endl;
for (int i = 1; i <= n; ++i) {
cerr << "STK " << i << " : ";
deque<int> p = q[i];
while (!p.empty()) cerr << p.front() << ' ', p.pop_front();
cerr << endl;
} cerr << endl;
}
inline void push(int x) {
res.push_back(make_pair(1, make_pair(x, 0))); int y = c[m--];
remove(x);
if (q[x].empty() || q[x].back() != y) q[x].push_back(y);
else q[x].pop_back();
add(x);
}
inline void clear(int x, int y) {
res.push_back(make_pair(2, make_pair(x, y)));
if (q[x].empty() || q[y].empty() || q[x].front() != q[y].front()) { assert(false); }
remove(x); remove(y); q[x].pop_front(); q[y].pop_front(); add(x); add(y);
}
int pt[N];
int main() {
T = read();
while (T--) {
n = read(); m = read(); k = read();
for (int i = 1; i <= m; ++i) c[i] = read();
for (int i = 1; i <= n; ++i) emp.insert(i), S.insert(i);
reverse(c + 1, c + m + 1);
while (m) {
int y = c[m];
if (tp[y]) { push(tp[y]); continue; }
if (bt[y]) { int x = *emp.begin(); int z = bt[y]; push(x); clear(x, z); continue; }
bool flag = 0;
for (int i : S) {
if (i != *emp.begin()) {
push(i);
flag = 1; break;
}
} if (flag) continue; int e = *emp.begin();
int l = m - 1; while (tp[c[l]]) pt[c[l]] = tp[c[l]], --l; int v = c[l];
if (v == y) { push(e); while (m > l) push(pt[c[m]]); push(e); continue; }
int w = q[bt[v]].back(); int p = bt[v]; int cnt = 0;
for (int i = m - 1; i > l; --i) cnt += (c[i] == w);
if (cnt & 1) {
push(e);
while (m > l) {
if (c[m] == w) push(p);
else push(pt[c[m]]);
} push(p);
continue;
}
push(p);
while (m > l) {
if (c[m] == w) push(p);
else push(pt[c[m]]);
} push(e); clear(e, p);
} printf("%d\n", res.size());
for (pair<int, pair<int, int> > i : res) {
printf("%d ", i.first);
if (i.first == 1) printf("%d\n", i.second.first);
else printf("%d %d\n", i.second.first, i.second.second);
} emp.clear(); S.clear();
for (int i = 1; i <= n; ++i) assert(q[i].empty());
for (int i = 0; i <= k; ++i) pt[i] = tp[i] = bt[i] = 0;
res.clear();
} return 0;
}