喵了个喵

· · 题解

include<bits/stdc++.h>

using namespace std; typedef long long ll; template<typename T>void rd(T&x){ x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x10+c-48;c=getchar();} x=f; } const int N=310,M=2e6+10,K=N*2; int T,n,m,k,a[M]; int o[M],p[M],b,c[K],c2[K]; int s[N][2],t[N]; int f[N],e[N],z,e2[N],z2; void ins(int x){ if(t[x]==1)e2[f[x]=z2++]=x; else if(!t[x])e[f[x]=z++]=x; } void del(int x){ if(t[x]==1)f[e2[--z2]]=f[x],e2[f[x]]=e2[z2]; else if(!t[x])f[e[--z]]=f[x],e[f[x]]=e[z]; } void ins(int y,int i){int x=a[i];del(y);o[i]=0;p[i]=y;c[x]=y;s[y][t[y]++]=x;ins(y);} void del(int y,int i){int x=a[i];del(y);o[i]=0;p[i]=y;c[x]=0;--t[y];ins(y);} void con(int y,int i){int x=a[i];del(y);o[i]=e[0];p[i]=y;c[x]=0;++b;s[y][0]=s[y][1];--t[y];ins(y);} int main(){ rd(T); while(T--){ rd(n);rd(m);rd(k);b=m; memset(c,0,(k+5)<<2); memset(t,0,(n+5)<<2); memset(f,0,(n+5)<<2); z=z2=0; for(int i=n;i;--i)ins(i); for(int i=1;i<=m;++i)rd(a[i]); for(int i=1,j=1;i<=m;i=++j){ int x=a[i]; if(int y=c[x]){ if(s[y][t[y]-1]==x)del(y,i); else con(y,i); }else if(z2||z>1)ins(z2?e2[z2-1]:e[z-1],i); else for(j=i+1;;++j){ if(x==a[j]){int y=e[0];ins(y,i);del(y,j);break;} if(int y=c[a[j]]){ if(s[y][t[y]-1]==a[j]){ del(y,j); if(!t[y]){ins(e[0],i);break;} c2[a[j]]=y; }else{con(y,j);ins(y,i);break;} }else ins(c2[a[j]],j); } } printf("%d\n",b); for(int i=1;i<=m;++i){ if(o[i])printf("1 %d\n2 %d %d\n",o[i],p[i],o[i]); else printf("1 %d\n",p[i]); } } }