题解 P8023【[ONTAK2015] Tasowanie】

rui_er · 2022-02-09 11:00:42 · 个人记录

后缀数组。

我们对 A+B 求出 rk 数组，然后进行二路归并，取 rk 更小的那个位置即可。

等下，A+B 里面 A 的后面多了一整个 B 当后缀，为啥不会影响结果呢？

如果当前位置 A_i\ne B_j，显然在 rk 数组里面没有影响。如果 A_i=B_j 了，但存在第一个 A_{i+k}\ne B_{j+k} 的位置，是同理的。那么下面考虑如果 A_{i\dots}=B_{j\dots}，直到一个串结束。此时一个串是另一个串的前缀，这些都是相同的，先取哪个数列中的数没有关系。这时候按照 rk 数组排序，默认会先取 B 中的数，也就不会出问题。

于是这题就做完了，总复杂度就是 SA 的复杂度，这里我写的是倍增算法，就是 \mathcal{O}(n\log{n})。

UPD：被 HACK 了，修改了一下，在 A 串末尾加了个 +\infty，通过了 HACK 数据。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 4e5+5; 

int n1, n2, a[N], b[N], sa[N], rk[N], lst[N<<1], id[N], cnt[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
    scanf("%d", &n1);
    rep(i, 1, n1) scanf("%d", &a[i]);
    a[n1+1] = 2000;
    scanf("%d", &n2);
    rep(i, 1, n2) scanf("%d", &a[n1+i+1]);
    int n = n1 + n2 + 1, m = 2000;
    rep(i, 1, n) ++cnt[rk[i] = a[i]];
    rep(i, 1, m) cnt[i] += cnt[i-1];
    per(i, n, 1) sa[cnt[rk[i]]--] = i;
    for(int w=1,p=0;;w<<=1,m=p) {
        p = 0;
        per(i, n, n-w+1) id[++p] = i;
        rep(i, 1, n) if(sa[i] > w) id[++p] = sa[i] - w;
        memset(cnt, 0, sizeof(cnt));
        rep(i, 1, n) ++cnt[rk[id[i]]];
        rep(i, 1, m) cnt[i] += cnt[i-1];
        per(i, n, 1) sa[cnt[rk[id[i]]]--] = id[i];
        memcpy(lst, rk, sizeof(rk));
        p = 0;
        rep(i, 1, n) {
            if(lst[sa[i]] == lst[sa[i-1]] && lst[sa[i]+w] == lst[sa[i-1]+w]) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
        }
        if(p == n) {
            rep(i, 1, n) sa[rk[i]] = i;
            break;
        }
    }
    for(int l=1,r=n1+2,i=1;i<=n;i++) {
        if(l > n1) b[i] = a[r++];
        else if(r > n) b[i] = a[l++];
        else b[i] = (rk[l] < rk[r]) ? a[l++] : a[r++];
    }
    rep(i, 1, n) printf("%d%c", b[i], " \n"[i==n]);
    return 0;
}