自动搬运

查看原文

来自洛谷，原作者为

	Wind_Leaves_ShaDow 别摆了。

搬运于2025-08-24 23:04:04，当前版本为作者最后更新于2024-10-15 14:41:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单小清新构造。

题意就是你可以对这个数列涂颜色，涂上去的新颜色会覆盖原本的颜色，每个颜色都只能涂一遍，然后要你构造一个操作序列得到最后的数组。

找到一个颜色第一次出现和最后一次出现的位置 $l_i,r_i$，我们在 $[l_i,r_i]$ 这个区间涂上这个颜色，然后里面的颜色就是覆盖在原颜色上面的。所以里面如果出现左右端点超过 $l_i,r_i$ 的颜色 $j$ 就可以判断无解。

否则你递归进去涂下一个颜色就是了。

为什么要写线段树。时间复杂度 $O(n)$。

#include <bits/stdc++.h>
#define lint __int128
//#define int long long
#define Il inline
#define Rg register
#define Ri Rg int
#define fi first
#define se second
#define vec vector
#define pb push_back
#define IT ::iterator
#define p_que priority_queue

using namespace std;
//typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=3e5;
const db eps=1e-9,pi=acos(-1.0);

int n,m,a[N+5],fl[N+5],fr[N+5];
bool hv=1;
queue<pair<int,pii>>ans;

Il void solve(int l,int r,int c){
	if(!hv||l>r)return;
	for(Ri i=l;i<=r;i++){
		if(a[i]==c)continue;
		if((i^fl[a[i]])||fr[a[i]]>r){hv=0;return;}
		ans.push({a[i],{i,fr[a[i]]}});solve(i+1,fr[a[i]]-1,a[i]);i=fr[a[i]];
	}
	return;
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>m>>n;
	for(Ri i=1;i<=m;i++){
		cin>>a[i];fr[a[i]]=i;
		if(!fl[a[i]])fl[a[i]]=i;
	}
	solve(1,m,0);
	if(!hv){cout<<-1;return 0;}cout<<ans.size()<<'\n'; 
	for(;!ans.empty();ans.pop())cout<<ans.front().fi<<' '<<ans.front().se.fi<<' '<<ans.front().se.se<<'\n';
	return 0; 
}