String Coloring (hard version)

Created by LXC on Wed Jan 17 10:29:34 2024

https://codeforces.com/problemset/problem/1296/E2

ranting: 2000

tag: data structures, dp

problem

给你一串长度为 $n$ 的字符串，你可以给每个位置上染上一种不大于 $n$ 的颜色

对于相邻的两个位置，如果他们的颜色不同则可以交换他们的位置

现在需要交换若干次后按照字典序排序

你需要找到最少满足条件的颜色数并输出方案

solution

对于一个升序的序列我们无需修改他们的相对位置。所以只需让整个数组拆分为尽量少的升序序列个数，每个升序序列涂同一种颜色就行了。

怎么样拆分尽量少的升序序列？

我们可以准备无数个“桶”，每个桶内装着拆分的升序序列。遍历字符串，对于每个字符ch，遍历每一个桶，一旦桶内最大字符大于ch则寻找下一个桶，而桶内最大字符小于等于ch（或者桶为空）则将ch放入该桶。

由于总共只有26个字符，所以最多也就只有26个桶。时间复杂度为$O(|\Sigma| n)$，$\Sigma$为字符集。

值得注意的是如果给的不是字符串而是数组，那么字符集$|\Sigma|$或许会很大。我们发现随着桶编号变大，桶内最大元素是非增长的。于是可以二分查找出第一个小于等于当前数字的桶编号。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t;
    vector<int> ans;
    for (int i=0; i<n; i++) {
        int l = 0, r = t.size();
        while (l<r) {
            int m = l+r>>1;
            if (t[m] <= s[i]) {
                r = m;
            } else {
                l = m+1;
            }
        }
        if (r == t.size()) t.push_back(s[i]);
        else t[r] = s[i];
        ans.push_back(r+1);
    }
    cout << t.size() << "\n";
    for (int i:ans) {
        cout << i << " ";
    } cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}