题意

给定 $n$ 个编号为 $1,2,\dots n$ 的初始为空的栈，同时给定一个值域为 $k\left(1\le k\le 2n-1\right)$ 的正整数序列 $\left\{a_n\right\}$。保证每种数的出现次数都是偶数。你可以进行若干次下列两种操作，要求最后每个栈和序列 $\left\{a_n\right\}$ 均为空，构造一种合法的操作序列。

1. 若 $\left\{a_n\right\}$ 非空，取出 $\left\{a_n\right\}$ 的第一个数 $a_1$ 并将其删去，同时任意选择一个栈 $t$，将 $k$ 插入 $t$ 的栈顶。此时，若栈 $t$ 栈顶两个数相同，则将其同时从栈 $t$ 中删去。
2. 选择两个非空的不同的栈 $i,j,i\neq j$，满足栈 $i,j$ 的栈底元素相同，则同时将 $i,j$ 的栈底的数删去。

多测，$n\le 300$，序列总长度 $\le 2\times 10^6$

题解

$k=2n-2$ 时的做法非常显然：我们保证第一个栈永远是空的，然后剩下 $n-1$ 个栈中的牌两两不同，且任意一个栈的大小 $\le 2$，称其为性质 $1$

加入一张牌时，如果这张牌已经存在。若在栈顶，则可以直接消掉。否则，可以加入一个空的栈然后用 $2$ 操作消掉。

否则，随便找一个 $\le 2$ 的栈插入，优先插入大小为 $1$ 的栈，这样一定能继续满足性质 $1$，因为 $k=2n-2$

$k=2n-1$ 的时候我们希望几乎所有时刻都是满足性质 $1$ 的。

此时，唯一一种和 $k=2n-2$ 时不同的情况是，如果当前有 $n-1$ 个大小为 $2$ 的栈，里面有 $1,2,\dots 2n-2$ 这些牌。且当前要加入的是牌 $a_i=k=2n-1$，唯一一个空的栈是栈 $q$。

那么，我们往后找到第一个位置 $j\gt i$ 满足 $a_j=a_i$ 或 $a_j$ 位于某一个栈的底部。

$1^{\circ}$ $a_j=a_i$

对于 $a_{i+1},a_{i+2}\dots a_{j-1}$ 这些牌，我们假设在插入 $a_i$ 之前牌 $t\left(1\le t\lt k\right)$ 的栈编号为 $p_t$，那么我们每次将 $a_{l}$ 插入 $p_{a_l}$ 的栈顶。

若 $p_{a_l}$ 的栈顶为 $a_l$ 则直接消去，否则 $p_{a_l}$ 这个栈大小为 $1$，直接将 $a_l$ 再插入栈顶。

而 $a_i,a_j$ 直接均插入栈 $q$ 即可，最后会消掉

$2^{\circ}$ $a_j\neq a_i$

此时我们假设插入 $a_i$ 前 $a_j$ 上方的那张牌为 $w$，令 $r$ 为 $a_{i},a_{i+1},\dots a_{j}$ 中 $w$ 的出现次数，$e$ 为 $a_j$ 所在栈的编号。

此时对于 $a_{i},a_{i+1},\dots a_{j}$ 中 $\neq a_j,\neq a_i,\neq w$ 的牌的处理方式和前一种一样。

若 $r=0$，则先将 $a_i$ 插入栈 $e$，最后将 $a_j$ 插入栈 $q$，应用一次 $2$ 操作，最后栈 $e$ 自底向上为 $w,a_i$，满足条件

若 $r$ 为正奇数，则先将 $a_i$ 插入栈 $q$，每次将 $w$ 插入栈 $e$，最后将 $a_j$ 插入栈 $e$。由于 $r$ 为奇数。$w$ 会消掉，把 $a_j$ "暴露" 出来，因此最后栈 $e$ 是空的。

若 $r$ 为正偶数，则先将 $a_i$ 插入栈 $q$，除了最后一个 $w$ 是插入栈 $q$ 以外 $a_j$ 和 $w$ 的插入方式和前一种一样。

最后栈 $e$ 为空，栈 $q$ 自底向上为 $a_i,w$。满足性质 $1$。

写起来很繁琐。最后的复杂度为 $\mathcal{O}\left(\sum n+\sum m\right)$

Code

#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_set>
using ll=long long;
constexpr int N(610),S(2e6+10);
std::unordered_set<int> s[5];
int pos[N<<1][2];
int stk[N<<1][5],cnt[N<<1];
int ops[S<<1][3],opc;
void ins(int v,int t)
{
    ++opc;ops[opc][0]=1;
    ops[opc][1]=t;
    s[cnt[t]].erase(t);
    if(cnt[t] && stk[t][cnt[t]]==v)
    {
        s[--cnt[t]].insert(t);
        pos[v][0]=pos[v][1]=0;
    }
    else
    {
        s[++cnt[t]].insert(t);
        stk[t][cnt[t]]=v;
        pos[v][0]=t;pos[v][1]=cnt[t];
    }
}
void op2(int v,int p,int q)
{
    ++opc;ops[opc][0]=1;
    ops[opc][1]=q;
    ++opc;ops[opc][0]=2;
    ops[opc][1]=p;ops[opc][2]=q;
    pos[v][0]=pos[v][1]=0;
    s[cnt[p]].erase(p);
    s[--cnt[p]].insert(p);
    for(int i(1);i<=cnt[p];++i)
    {
        int v(stk[p][i+1]);
        stk[p][i]=v;pos[v][1]=i;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T,n,m,k;
    std::cin>>T;
    while(T--)
    {
        std::cin>>n>>m>>k;
        static int a[S];
        for(int i(1);i<=m;++i) std::cin>>a[i];
        for(int i(0);i<5;++i) s[i].clear();
        for(int i(1);i<=n;++i) s[0].insert(i),cnt[i]=0;
        for(int i(1);i<=k;++i) pos[i][0]=pos[i][1]=0;
        opc=0;
        for(int i(1);i<=m;++i)
        {
            int v(a[i]);
            if(pos[v][0])
            {
                int t(pos[v][0]);
                if(pos[v][1]==cnt[t])
                {
                    ins(v,t);
                }
                else
                {
                    int q(*s[0].begin());
                    op2(v,t,q);
                }
            }
            else
            {
                if(s[0].size()>1 || !s[1].empty())
                {
                    int t;
                    if(s[0].size()>1) t=*s[0].begin();
                    else t=*s[1].begin();
                    ins(v,t);
                }
                else
                {
                    int t=*s[0].begin();
                    int j(i+1);
                    static int mm[N];
                    while(!(a[j]==v || pos[a[j]][1]==1))
                    {
                        mm[a[j]]=pos[a[j]][0];
                        ++j;
                    }
                    if(a[j]==v)
                    {
                        ins(v,t);
                        for(int l(i+1);l<j;++l) ins(a[l],mm[a[l]]);
                        ins(v,t);
                    }
                    else
                    {
                        int q(pos[a[j]][0]),u(stk[q][cnt[q]]);
                        int k(0);
                        for(int l(i+1);l<j;++l) if(a[l]==u)
                        {
                            ++k;
                        }
                        if(!k)
                        {
                            ins(v,q);
                            for(int l(i+1);l<j;++l) ins(a[l],mm[a[l]]);
                            op2(a[j],q,t);
                        }
                        else
                        {
                            if(k&1^1)
                            {
                                int r(j-1);
                                while(a[r]!=u) --r;
                                ins(v,t);
                                for(int l(i+1);l<j;++l)
                                {
                                    if(l!=r) ins(a[l],mm[a[l]]);
                                    else ins(a[l],t);
                                }
                                ins(a[j],q);
                            }
                            else
                            {
                                ins(v,t);
                                for(int l(i+1);l<j;++l) ins(a[l],mm[a[l]]);
                                ins(a[j],q);
                            }
                        }
                    }
                    i=j;
                }
            }
        }
        std::cout<<opc<<"\n";
        for(int i(1);i<=opc;++i)
        {
            int tp(ops[i][0]),s1(ops[i][1]),s2(ops[i][2]);
            if(tp==1)
            {
                std::cout<<"1 "<<s1<<"\n";
            }
            else
            {
                std::cout<<"2 "<<s1<<" "<<s2<<"\n";
            }
        }
    }
    return 0;
}