题解：P11080 [ROI 2019 Day 1] 拍照

_Wind_Leaves_ShaDow_ · 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; 
}