lessons/参考实现/04-KMP与Manacher/AtCoder-qupc2018_h.cpp

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent;
    explicit DSU(int n = 0) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) parent[b] = a;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> radius(n);
    for (int &x : radius) {
        cin >> x;
        x = (x - 1) / 2;
    }

    int levels = 1;
    while ((1 << levels) <= n) ++levels;
    vector<int> count(levels), length(levels);
    vector<DSU> dsu;
    dsu.reserve(levels);
    for (int k = 0; k < levels; ++k) {
        length[k] = 1 << k;
        count[k] = n - length[k] + 1;
        dsu.emplace_back(2 * count[k]);
    }
    for (int i = 0; i < n; ++i) dsu[0].unite(i, count[0] + i);

    auto node = [&](int k, int start, bool reversed) {
        return start + (reversed ? count[k] : 0);
    };
    for (int center = 0; center < n; ++center) {
        int remaining = radius[center];
        int offset = 0;
        while (remaining > 0) {
            int k = 31 - __builtin_clz(remaining);
            int block = 1 << k;
            int left_start = center - radius[center] + offset;
            int right_start = center + radius[center] - offset - block + 1;
            dsu[k].unite(node(k, left_start, false), node(k, right_start, true));
            offset += block;
            remaining -= block;
        }
    }

    for (int k = levels - 1; k >= 1; --k) {
        int half = 1 << (k - 1);
        auto children = [&](int id) {
            bool reversed = id >= count[k];
            int start = id - (reversed ? count[k] : 0);
            if (!reversed) {
                return pair<int, int>{node(k - 1, start, false),
                                      node(k - 1, start + half, false)};
            }
            return pair<int, int>{node(k - 1, start + half, true),
                                  node(k - 1, start, true)};
        };
        for (int id = 0; id < 2 * count[k]; ++id) {
            int root = dsu[k].find(id);
            if (root == id) continue;
            auto [a1, a2] = children(id);
            auto [b1, b2] = children(root);
            dsu[k - 1].unite(a1, b1);
            dsu[k - 1].unite(a2, b2);
        }
    }

    vector<vector<int>> unequal(n);
    for (int center = 0; center < n; ++center) {
        int left = center - radius[center] - 1;
        int right = center + radius[center] + 1;
        if (left >= 0 && right < n) {
            int a = dsu[0].find(left);
            int b = dsu[0].find(right);
            unequal[a].push_back(b);
            unequal[b].push_back(a);
        }
    }

    vector<vector<int>> members(n);
    for (int i = 0; i < n; ++i) members[dsu[0].find(i)].push_back(i);
    vector<int> roots;
    for (int i = 0; i < n; ++i) if (!members[i].empty()) roots.push_back(i);
    sort(roots.begin(), roots.end(), [&](int a, int b) {
        return members[a][0] < members[b][0];
    });

    vector<int> color(n, -1);
    for (int root : roots) {
        bool forbidden[26] = {};
        for (int to : unequal[root]) {
            to = dsu[0].find(to);
            if (color[to] != -1) forbidden[color[to]] = true;
        }
        int chosen = 0;
        while (chosen < 26 && forbidden[chosen]) ++chosen;
        if (chosen == 26) return 1;  // The statement guarantees this cannot happen.
        color[root] = chosen;
    }

    string answer(n, 'a');
    for (int i = 0; i < n; ++i) answer[i] += color[dsu[0].find(i)];
    cout << answer << '\n';
    return 0;
}