题解 - 题解 - 青藤 OJ

原题链接：https://codeforces.com/gym/102803/problem/E

题解 1

考虑 SA 中相邻的元素，也就是排名相邻的两个串。如果你知道 Height，相当于你就知道了对字符的相等关系，和末尾一对字符的小于关系。对于相等关系，可以用并查集合并。

如果你不知道 Height，那也可以通过判断它后面的字符串的大小关系确定能不能相等。即，对于后缀，的字典序小于。如果字典序小于，那么位置的字符可以取等，否则必须。判断的字典序可以通过求 SA 的逆数组得到。

然后把这些小于关系在并查集合并后的点上连边，那实际上就是找一个字典序最小拓扑序。可以按照 SA 的顺序贪心，每个合并后的点放能放的最小值，这样一定是字典序最小的（因为每个字符都是最小的）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
 
const int MAXn = 5005;
int sa[MAXn], hei[MAXn], rk[MAXn], val[MAXn];
 
 
int g[MAXn];
int f(int x) {
    return g[x] = (g[x] == x ? x : f(g[x]));
}
void mg(int a, int b) {
    a = f(a), b = f(b);
    g[a] = b;
}
 
vector<int> v[MAXn];
 
void add(int x, int y) {
    // x < y
    v[y].pb(x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> sa[i], rk[sa[i]] = i;
    for (int i = 1; i < n; i++)
        cin >> hei[i];
    for (int i = 1; i <= n + 1; i++)
        g[i] = i;
    rk[n + 1] = 0;
    for (int i = 1; i < n; i++) {
        if (hei[i] != -1) {
            for (int j = 0; j < hei[i]; j++)
                mg(sa[i] + j, sa[i + 1] + j);
        }
    }
 
    for (int i = 1; i < n; i++) {
        if (hei[i] != -1) {
            add(f(sa[i] + hei[i]), f(sa[i + 1] + hei[i]));
        }
        if (rk[sa[i] + 1] > rk[sa[i + 1] + 1])
            add(f(sa[i]), f(sa[i + 1]));
    } 
    val[n + 1] = -1;
    for (int i = 1; i <= n; i++)
        val[i] = -2;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        int t = f(sa[i]);
        if (val[t] != -2) {
            assert(val[t] == cur);    
            continue;
        }
        for (ll x : v[t]) {
            assert(val[x] != -2);
            cur = max(cur, val[x] + 1);
        }
        assert(cur < 26);
        val[t] = cur;
    }
    for (int i = 1; i <= n; i++)
        cout << (char)('a' + val[f(i)]);
    cout << endl;
}

题解 2

如果知道height，就能得到一堆相等关系和一个不等关系。

的问题，可以通过讨论和的关系得到

然后跑个差分约束即可

考虑相等的可以用并查集缩起来，这里每次相等的条件是区间对区间，所以可以写个倍增并查集，那这个题就能出到1e5拉！