「找性质」 [Codeforces 1209G1] Into Blocks (easy version)

· · 题解

感觉这个 G1 还是比较 naive 的？找个性质这题就没了。

大概做题时有这么几个 Observation，当时拿笔写了下来，感觉应该是比较正常思路：

1、答案上界一定是 n-\max \{col{\rm num}\} .

2、如果一个颜色存在不相邻，那么要么会被全部涂成别的颜色，要么会被保留。

3、根据 2 不难发现，一段交错排布的元素最后必然只会保留一种颜色。

4、根据 3 可以得到一个贪心：将所有颜色按照出现次数从大到小排序。一开始预处理出所有颜色第一次出现的位置 s_i 和最后一次出现的位置 t_i，那么不难看出要把 [s_i,t_i] 之间的元素都涂成当前颜色。不难知道这样是最优的。

然后实现上遇上了一点小阻碍。大概就是说随着不停地染色，可能会有一些别的颜色被染成当前颜色，这样就要动态更新当前颜色的 s_i 和 t_i 。然后就因为觉得这个不好维护就摸了一会儿…结果发现其实是很好维护的。具体来说，从大到小做一定可以让每个点至多被染一次色，复杂度可以保证；同时发现 [s_i,t_i] 分别满足单调性，就可以暴力 while 做了。

最后复杂度显然排序外线性。


int ans ;
int cnt ;
int n, q ;
int buc[N] ;
int fst[N] ;
int lst[N] ;
int vis[N] ;
int base[N] ;
pint ord[N] ;
vint pos[N] ;

#define m_k make_pair

bool comp(pint a, pint b){
    return a.fr == b.fr ? a.sc < b.sc : a.fr > b.fr ;
}

int main(){
    cin >> n >> q ; int x, y ;
    for (int i = 1 ; i <= n ; ++ i)
        base[i] = qr(), buc[base[i]] ++ ;
    for (int i = 1 ; i <= n ; ++ i)
        pos[base[i]].push_back(i) ;
    for (int i = 1 ; i <= n ; ++ i)
        if (!fst[base[i]]) fst[base[i]] = i ;
    for (int i = n ; i >= 1 ; -- i)
        if (!lst[base[i]]) lst[base[i]] = i ;
    for (int i = 1 ; i <= 200000 ; ++ i)
        if (buc[i]) ord[++ cnt] = m_k(buc[i], i) ;
    sort(ord + 1, ord + cnt + 1, comp) ;
    for (int i = 1 ; i <= cnt ; ++ i){
        x = ord[i].fr ; y = ord[i].sc ;
        if (vis[y]) continue ; vis[y] = 1 ;
        if (x == lst[y] - fst[y] + 1) continue ;
        int l = fst[y], r = lst[y] ;
        for (int p = fst[y] ; p <= lst[y] ; ++ p){
//            printf("%d ", p) ;
            if (base[p] != y && !vis[base[p]]){
                vis[base[p]] = 1 ;
//                printf("%d ", base[p]) ;
                for (auto k : pos[base[p]]){
                    chkmin(l, k) ;
                    chkmax(r, k) ;
                    base[k] = y, ++ ans ;
                }
            }
//            puts("") ;
        }
//        printf("%d %d\n", l, r) ;
        while (1){
            int tl, tr ;
//            printf("%d %d\n", l, r) ;
            tl = fst[y], tr = lst[y] ;
            if (l == fst[y] && r == lst[y]) break ;
            fst[y] = l, lst[y] = r ;
            for (int p = tl - 1 ; p >= l ; -- p){
//                printf("(%d %d %d)", p, base[p], vis[base[p]]) ;
                if (base[p] != y && !vis[base[p]]){
                    vis[base[p]] = 1 ;
//                    printf("%d ", base[p]) ;
                    for (auto k : pos[base[p]]){
                        chkmin(l, k) ;
                        chkmax(r, k) ;
                        base[k] = y, ++ ans ;
                    }
                }
//                puts("") ;
            }
            for (int p = tr + 1 ; p <= r ; ++ p){
                if (base[p] != y && !vis[base[p]]){
                    vis[base[p]] = 1 ;
                    for (auto k : pos[base[p]]){
                        chkmin(l, k) ;
                        chkmax(r, k) ;
                        base[k] = y, ++ ans ;
                    }
                }
            }
        }
//        debug(base, 1, n) ;
//        printf("%d %d %d %d %d\n", x, y, fst[y], lst[y], ans) ;
    }
    printf("%d\n", ans) ;
    return 0 ;
}

把最后一个 for 里 if 的 y 写成了 x 导致 Wa On 7 呜呜呜。