记录编号	581814	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2022] 喵了个喵	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	5.768 s
提交时间	2023-08-14 20:39:54	内存使用	10.88 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 310,M = 2e6+10;
int T,n,m,k;
int a[M],id[2*N];//a为原数组
//id为某种牌所在栈编号,没有则为0 
struct made{
	int v1,v2;
}; 
int stp;//辅助栈编号 
deque<int>st[N];//每个栈 
queue<int>q;//队列维护空栈 
vector<made>ans;//答案 
void first_() {
	ans.clear();//清空答案 
	stp = n;//最开始辅助栈定为n 
	memset(id,0,sizeof(id));//初始化 
}
void pu(int x,int y){
	ans.push_back((made){x,y});
}//方便记答案 
bool simple(int x){//普通相消 
	int stx = id[x];//x所在栈 
	if(!stx){//该x未在栈内 
		if(q.empty())return false;//所有栈都满了,开始特殊处理 
		id[x] = stx = q.front();//x入进队头的栈并记录 
		q.pop();
		pu(stx,0);//入编号为stx的栈 
		st[stx].push_back(x);//入栈 
	}
	else{
		q.push(stx);//元素弹出,多了一个栈的位置 
		if(st[stx].back() == x){//栈顶相等 
			pu(stx,0);//直接入该栈相消 
			st[stx].pop_back();
		}
		else{//栈底相等 
			pu(stp,0);//首先放到辅助栈里
			pu(stx,stp);//按照操作2相消 
			st[stx].pop_front();//栈底出栈 
		}
		id[x] = 0;//更新id,消除掉则x未在栈内 
	}
	return true;
}
int main(){
	freopen("noip2022_meow.in","r",stdin);
	freopen("noip2022_meow.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);//n个栈 m个卡牌 k种卡牌 
		first_();
		for(int i = 1;i <= m;i++) 
			scanf("%d",&a[i]);//离线操作
		while(!q.empty())q.pop();
		for(int i = 1;i < n;i++){q.push(i);q.push(i);}
		for(int i = 1;i <= m;i++){
			if(!simple(a[i])){//当栈都满了以后 
				int now = a[i],nx = i+1;int x = a[nx];
				for(;nx <= m && x != now && x == st[id[x]].back();nx++,x = a[nx]);
				//找到now后第一个在栈底的元素 
				//此时nx是i后第一个不在栈顶上的下标，x是a[nx]
				if(x == now){//X=P 
					pu(stp,0);//将p入到辅助栈内 
					for(int j = i+1;j < nx;j++)simple(a[j]);//中间正常 
					pu(stp,0);//最后再将p入到辅助栈内消掉,辅助栈不变 
				}
				else{
					int stx = id[x];//X所在栈 
					int y = st[stx].back();//X所在栈顶Y 
					bool flag = true;//判断奇偶数 
					for(int j = i+1;j < nx;j++)//栈顶Y出现次数 
					    if(a[j] == y)flag = !flag;
					if(flag){//偶数 
						pu(stx,0);//将P放到X所在栈 
						st[stx].push_back(a[i]);
						for(int j = i+1;j < nx;j++){
							if(a[j] == y)pu(stp,0);//将Y全部放到辅助栈内相消,辅助栈依旧为空 
							else simple(a[j]);//其他普通相消 
						}
						pu(stp,0);pu(stx,stp);//最后把X放到辅助栈内用操作2相消 
						st[stx].pop_front();//栈底出栈 
						id[x] = 0;id[now] = stx;//更新,P的栈为X的栈,X被消掉了没有栈
						//id[y] = 0;全部消掉了,本来就是0,变不变都行 
					}
					else{//奇数 
						pu(stp,0);//将P放到辅助栈 
						st[stp].push_back(now);//入栈 
						id[now] = stp;//更新P在辅助栈内 
						q.push(stp);//辅助栈还有一个元素的位置 
						for(int j = i+1;j < nx;j++){
							if(a[j] == y)pu(stx,0);//将全部Y入到X的栈内,Y全部消掉,最后只剩X 
							else simple(a[j]);//剩下正常相消 
						}
						pu(stx,0);//将X放到该栈相消,该栈现在为空 
						st[stx].clear();
						//清空当前栈 
						id[x] = id[y] = 0;//更新,X,Y全部被消掉 
						stp = stx;//当前栈为空,辅助栈进了P
						//将该栈更新为辅助栈 
					}
				}
				i = nx;//因为循环内i会自动++,所以只需要赋值为r,自动r+1 
			} 
		}
		printf("%d\n",ans.size());
		for(int i = 0;i < ans.size();i++){//从0开始 
			if(ans[i].v2)printf("2 %d %d\n",ans[i].v1,ans[i].v2);
			else printf("1 %d\n",ans[i].v1);
		}
	}
	
	
	return 0;
	
}