题目描述

给定一个长度为 的环状字符串。

将这个字符串划分成 段，每段长度为 ，这个划分的代价为字典序最大的划分子段。

求所有划分方案下，字典序最小的划分代价。

题目太难描述了自己看题吧。

正解

环状字符串按照套路先倍长，然后枚举起始位置就能枚举到所有的划分了。

现在问题就是如何快速求出一个划分的代价。

考虑后缀排序，求出每一个后缀的排名。

然后一个划分的代价其实就是区间（并不连续，类似于区间 ）的排名取 max。

这个可以用线段树或者单调队列做，时间复杂度 / 。

总复杂度 。

吐槽

这题后缀排序怎么卡二分 + 哈希啊，让我这种不会 SA 的人怎么活啊。（我的 SA 是直接蒯 Luogu 题解的

upd : 好像后面重测我的二分 + 哈希又活过来了。

#include <bits/stdc++.h>
#define N 1000005

using namespace std;

int n, m, k, rlim;
int mac[N];
int S, rak[N], sa[N], tax[N], tp[N];
char s[N];

void Qsort() {
    for (int i = 0; i <= S; i++) tax[i] = 0;
    for (int i = 1; i <= n; i++) tax[rak[i]]++;
    for (int i = 1; i <= S; i++) tax[i] += tax[i - 1];
    for (int i = n; i >= 1; i--) sa[ tax[rak[tp[i]]]-- ] = tp[i];
}
void SuffixSort() {
    S = 75;
    for (int i = 1; i <= n; i++) rak[i] = s[i] - '0' + 1, tp[i] = i;
    Qsort();
    for (int w = 1, p = 0; p < n; S = p, w <<= 1) {
        p = 0;
        for (int i = 1; i <= w; i++) tp[++p] = n - w + i;
        for (int i = 1; i <= n; i++) if (sa[i] > w) tp[++p] = sa[i] - w;
        Qsort();
        swap(tp, rak);
        rak[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
    }
}

int que[N];

int main() {
    scanf("%d %d %s", &n, &m, s + 1), k = n / m;
    for(int i = 1; i <= n; ++i)
        s[i + n] = s[i];

    n <<= 1, rlim = n - m + 1;
    SuffixSort();
    n >>= 1;

    for(int i = 1; i <= m; ++i) {
        int hd = 1, tl = 0;
        for(int j = i; j <= rlim; j += m) {
            while(hd <= tl && j - que[hd] >= n) ++hd;
            while(hd <= tl && rak[j] > rak[que[tl]]) --tl;
            que[++tl] = j;
            if(j - m * (k - 1) > 0)
                mac[j - m * (k - 1)] = rak[que[hd]];
        }
    }

    mac[0] = N;
    int mpos = 0;
    for(int i = 1; i <= n; ++i)
        if(mac[i] < mac[mpos])
            mpos = i;

    int str = sa[mac[mpos]];
    for(int i = 0; i < m; ++i)
        putchar(s[str + i]);
    putchar('\n');
    return 0;
}