manacher + dsu

原题:https://atcoder.jp/contests/abc349/tasks/abc349_g

AC记录:https://atcoder.jp/contests/abc349/submissions/52786070

#include <bits/stdc++.h>

class dsu {
    public:
        std::vector<int> p;
        int n;

        dsu(int _n) : n(_n) {
            p.resize(n);
            std::iota(p.begin(), p.end(), 0);
        }

        inline int get(int x) {
            return (x == p[x] ? x : (p[x] = get(p[x])));
        }

        inline void unite(int x, int y) {
            x = get(x);
            y = get(y);
            if (x != y) {
                p[x] = y;
            }
        }
};

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

    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (auto& _ : A) {
        std::cin >> _;
    }

    dsu d(N);
    for (int i = 1, j = -1, r = 0; i < N; i++, j--) {
        int it;
        if (i > r) {
            r = i, it = 0;
        } else {
            it = A[j];
        }
        if (it + i >= r) {
            it = r - i;
            int b = r, a = 2 * i - r;
            while (a - 1 >= 0 && b + 1 < N && it < A[i]) {
                a--, b++;
                it += 1;
                d.unite(a, b);
            }
            j = i, r = b;
        }
        if (it != A[i]) {
            std::cout << "No\n";
            return 0;
        }
    }
    std::vector<int> who(N);
    for (int i = 0; i < N; i++) {
        who[i] = d.get(i);
    }
    std::vector<std::vector<int>> g(N);
    for (int i = 0; i < N; i++) {
        int a = i - A[i] - 1;
        int b = i + A[i] + 1;
        if (a >= 0 && b < N) {
            if (who[a] == who[b]) {
                std::cout << "No" << '\n';
                return 0;
            }
            g[who[a]].push_back(who[b]);
            g[who[b]].push_back(who[a]);
        }
  }
    std::vector<int> num(N, 0);
    std::cout << "Yes\n";
    for (int i = 0; i < N; i++) {
        int x = who[i];
        if (!num[x]) {
            std::set<int> ban;
            for (auto y : g[x]) {
                ban.insert(num[y]);
            }
            num[x] = 1;
            while (ban.count(num[x])) num[x]++;
        }
        std::cout << num[x] << " \n"[i == N];
    }

    return 0;
}