P9349题解

262620zzj · 2023-09-03 22:51:46 · 题解

首先读题后，如果直接按照题目模拟，每次放置新棋子就寻找之前的同一颜色棋子，那么复杂度 O(n^2) 显然超时了，不行。

低复杂度做法

定义最后一个颜色是 c 的棋子的位置是 last_c，1 \sim n 扫一遍数组，i \sim last_{color[i]} 区间颜色均为 color[i]，并且不会被其他染色操作所影响。

那为什么这样是对的呢？(以下简称 last_{color[i]} 为 lci）如果有其他的染色操作影响了 i \sim lci 这个区间的话，设影响该区间的区间为 l \sim r。

• 如果 l>lci，则 l \sim r 和 i \sim lci 不相交。

• 如果 l<lci 且 r<lci，则 l \sim r 被 i \sim lci 覆盖，可以略去。

• 如果 l<lci 且 r>lci，则在遍历到 r 之前， i \sim lci 已经将 l 染色，此种情况不可能出现。

综上所述，以此方法将一段区间染色后，区间内棋子不会再改变颜色，这样就可以在每次染色之后直接令 i=lci+1，总复杂度 O(n)。

最后注意 A[i]\le10^9，所以用一个 map 解决下标过大的问题。

代码

#include<cstdio>
#include<map>
using namespace std;
const int N=2e5+5;
int n,color[N];
map<int,int> last; 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&color[i]);
        last[color[i]]=i;
    }
    for(int i=1;i<=n;i++){
        int lci=last[color[i]];
        for(int j=i+1;j<lci;j++)color[j]=color[i];
        i=lci;
    }
    for(int i=1;i<=n;i++)printf("%d\n",color[i]);
    return 0;
}