思路与算法

预处理每张牌同色下一次出现位置。每种当前未配对颜色只保留一张，记录所在栈。通常每栈至多两张，并留一个空栈；维护空栈集合、单牌栈按下一次出现排序的集合，以及“底牌先于顶牌再次出现”的危险双牌栈。 若新牌颜色已经存在：在顶部则直接放入自动消除；在底部则把新牌放保留空栈，再执行两栈底部消除。若是新颜色，优先填单牌栈或使用多余空栈。恰一空栈且其余全双牌时，若存在危险双牌栈，把新牌叠其上成为唯一三牌栈，空栈仍留；否则把新牌放最后空栈，进入无空栈状态。 无空栈时遇新颜色，选择下一次出现最晚的单牌栈叠放。由于k≤2n-1，新颜色到来时至少有两根单牌栈。每次集合状态随栈修改同步删除和重插；消除单牌栈后重新获得空栈。输出每次放牌与必要的底部消除操作。

正确性说明

保留空栈时底部重复能直接配对。唯一三牌栈由危险双牌栈叠加而来，其中间牌原顶牌的下一次出现晚于底牌，因此中间牌不会首先回来；先匹配顶部或底部即可把栈恢复到至多两张。 进入无空栈时所有双牌都安全，即顶牌先回来。之后对单牌栈叠放若产生危险双牌，选的是下一次出现最晚的单牌，故仍存在更早返回的单牌栈。保持不变量：所有危险双牌底牌的返回均晚于某个单牌的返回。因此在无空栈时期，下一次匹配不会需要取底部；若该更早单牌先配对，就已腾出空栈。新颜色时若只有一单牌与n-1双牌，则已保留2n-1种颜色，不能再有新颜色，故选择总可行。归纳每步能合法处理所有牌，偶数出现次数保证最后全部消除。每张输入牌一次放入，每次额外底部消除配掉两牌，故总操作≤m+m/2≤2m。

复杂度

预处理下一次出现O(m+k)，集合初始化O(n)，每张牌常数次有序集合操作O(log n)，总O(m log n+n+k)，空间O(m+n+k)，其中操作输出与next数组均O(m)。所有测试组总牌数≤2000000。

易错点

栈顶自动消除与两栈底部消除不同。特判允许不同栈但底色不同时的无效操作，不错误拒绝题意允许的无效果步骤；同栈编号不合法。代码真实换行，正常构造不依赖无效操作。满规模输出超过12MiB时用同一沙箱缓存文件读取，保持CPU/内存约束。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Op {
    int a, b, c;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> a(m), next(m), last(k + 1, m), expected(k + 1, m), owner(k + 1);
        for (int &x : a)
            cin >> x;
        for (int i = m - 1; i >= 0; i--) {
            next[i] = last[a[i]];
            last[a[i]] = i;
        }
        vector<deque<int>> s(n + 1);
        set<int> empty, unsafe;
        set<pair<int, int>> single;
        for (int u = 1; u <= n; u++)
            empty.insert(u);
        vector<Op> ops;
        ops.reserve(m + m / 2);
        auto eraseState = [&](int u) {
            if (s[u].empty())
                empty.erase(u);
            else if (s[u].size() == 1)
                single.erase({expected[s[u][0]], u});
            else if (s[u].size() == 2)
                unsafe.erase(u);
        };
        auto addState = [&](int u) {
            if (s[u].empty())
                empty.insert(u);
            else if (s[u].size() == 1)
                single.insert({expected[s[u][0]], u});
            else if (s[u].size() == 2 && expected[s[u][0]] < expected[s[u][1]])
                unsafe.insert(u);
        };
        for (int i = 0; i < m; i++) {
            int x = a[i], u = owner[x];
            if (u) {
                eraseState(u);
                if (s[u].back() == x) {
                    ops.push_back({1, u, 0});
                    s[u].pop_back();
                    owner[x] = 0;
                } else {
                    assert(s[u].front() == x && !empty.empty());
                    int e = *empty.begin();
                    eraseState(e);
                    ops.push_back({1, e, 0});
                    ops.push_back({2, u, e});
                    s[u].pop_front();
                    owner[x] = 0;
                    addState(e);
                }
                addState(u);
            } else {
                expected[x] = next[i];
                assert(next[i] < m);
                if (empty.empty()) {
                    assert(single.size() >= 2);
                    u = single.rbegin()->second;
                } else if (!single.empty())
                    u = single.begin()->second;
                else if (empty.size() >= 2)
                    u = *empty.begin();
                else if (!unsafe.empty())
                    u = *unsafe.begin();
                else
                    u = *empty.begin();
                eraseState(u);
                ops.push_back({1, u, 0});
                s[u].push_back(x);
                owner[x] = u;
                assert(s[u].size() <= 3);
                addState(u);
            }
        }
        assert(empty.size() == (size_t)n);
        assert(ops.size() >= (size_t)m && ops.size() <= (size_t)2 * m);
        cout << ops.size() << '\n';
        for (auto o : ops) {
            cout << o.a << ' ' << o.b;
            if (o.a == 2)
                cout << ' ' << o.c;
            cout << '\n';
        }
    }
}