[JOI 2023 Final] Stone Arranging 2

洛谷P9349

题意

一种区间覆盖操作，可以考虑直接无脑线段树,复杂度为\(O(nlog_n)\)。
但是观察后发现可以开一个桶，记录这个数在序列中出现的最后一次的下标。循环扫一遍原序列，从小到大对于每一个a[i]，使得下标i到m[a[i]]的区间全部覆盖为a[i]。每次覆盖一个小区间后，因为前面的区间已经被覆盖，对后续没有任何影响，所以我们可以让i直接跳到m[a[i]]+1，再进行下一次覆盖操作。这样就可以实现 \(O(n)\) 的复杂度。

#include<bits/stdc++.h>
#define MAXN 200086

using namespace std;

map<int ,int> m;
int n,a[MAXN],cnt;


int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        m[a[i]]=i;
        //cnt=max(a[i],cnt);
    }
    
    for(int i=1;i<=n;i=m[a[i]]+1){
        for(int j=i;j<=m[a[i]];j++){
            a[j]=a[i];
        }
    }

for(int i=1;i<=n;i++)cout<<a[i]<<'\n';

return 0;
}