题解 CF1621I 【Two Sequences】

· · 题解

fz 汉化组。

做法和证明基本上来源于官方题解和 ecnerwala 题解。

生肉太难啃了。（哭）

首先改写 op 操作的每一步。在第 i 步中，设找到的字典序最小的子串是 [l,l+i-1]，我们将这一步看作是：找一个 l，用 C[l,n-i+1] 替换 C_{n-i+1}，然后只保留前 n 个字符，使得字典序最小。然后我们会发现我们可以把“保留前 n 个字符”丢到最后考虑。

形式化一下，设 B_i 是 C[1,n-i+1] 的一个非空后缀，使得 B_i+B_{i-1}+\dots+B_1 最小，op(C) 就是 B_n+B_{n-1}+\dots+B_1 的前 n 个字符。

接着我们断言经过 O(\log\log n) 次 op 之后序列就不会改变了。注意到非升序列 op 以后不会改变，考虑证明这么多次 op 以后序列会变成非升。

考虑序列的最长非升前缀 C[1,r]，设其最后一段连续的相等字符的左端点是 l，考虑这段相等字符。在 C[1,l] 到 C[1,r+1] 这些前缀中，C_l 都是其中最小的字符，故 B_{n-r} 到 B_{n-l+1} 都从 l 开始。

那么，B_{n-l+1}+B_{n-l}+\dots+B_{n-r} 必然是 O((r-l)^2) 个 C_r 加上一个 C_{r+1}。又，对于 i>n-l_1 有 B_i=C[n-i+1,n-i+1]。故若 op(C) 不是非升（即这个 C_{r+1} 在前 n 个字符以内），那么这段连续的 C_r 必然是 op(C) 的上述“最长非升前缀的最后一段连续相等字符”。

这也就是说，一次 op 要么使序列变得非升，要么使这段连续相等字符的长度平方，那么有效的 op 操作最多进行 O(\log\log n) 次。通过把上面那段连续段的长度精确地算出来可以得出，在本题 n\le10^5 的范围内，op 操作只会进行 6 次，那么我们只需考虑如何以优秀的复杂度进行一次 op 操作。

令 S 是 C[1,n-i+1] 的最小后缀，我们断言 S 是 B_i 的整周期。考虑反证法，若不是这样，设 r=n-i+1，S 在 l 开头，B_i 在 x 开头，易证 S 是 B_i 的前缀。设 T=C[x+r-l,r]。 此时，T 一定是 B_{i-1}+B_{i-2}+\dots+B_1 的前缀。否则，若 T 小于它，则让 B_{i-1} 从 x+r-l 开始更优；若 T 大于它，则让 B_i=S 更优。

从前往后考虑 T 的每 r-l+1 个字符，即 T[1,r-l+1]，T[r-l+2,2r-2l+2]，等等。若它大于 S，则 B_{i-1} 从 l 开头会更优，故它小于等于 S。由于 S 不是 B_i 的整周期，所以 |T| 一定不是 r-l+1 的倍数。那么最后剩下长度小于 r-l+1 的后缀，同理它不能大于 S，所以它小于 S。但是它也是 C[1,r] 的后缀，与 S 是最小后缀矛盾。

至此，我们其实已经能够得到一些做法，比如官方题解给出的 O(n\log^2n\log\log n) 做法。但这还不够，下面介绍 ecnerwala 给出的 O(n\log\log n) 做法。

寻找更强的结论，我们继续断言：若 i=1 或 |B_{i-1}|=1，则 B_i 是 C[1,n-i+1] 的最小后缀 S，否则 B_i 是其循环尽量多整数次。

记 E=C_{n-i+2}+B_{i-2}+B_{i-3}+\dots+B_1。考虑 B_{i-1} 去掉最后一个字符得到的串，记为 A，其是 C[1,n-i+1] 的可能为空的后缀，使得 A+E 最小。B_i 则需要使得 B_i+A+E 最小。

首先注意到 S^k+T<S^{k+1}+T\Leftrightarrow S^{k-1}+T<S^k+T（两边同时在前面加上 S），于是 B_i 只可能是 S 或其循环尽量多次，并且其只取决于 A+E 和 S+A+E 的大小关系。

注意到 S 也是 C[1,n-i+1] 的后缀，那么我们知道 A+E<S+E。若 A 为空，此式等价于 A+E<S+A+E。否则，我们知道 S 是 A 的前缀，设 A 去掉前缀 S 为 A'，我们有 A+E<A'+E\Rightarrow S+A+E<A+E。A 为空等价于 |B_{i-1}|=1，那么我们证明了本节开头提到的结论。

接下来，剩下的问题就只有如何对一个串的每个前缀找出其最小后缀和这个后缀的最大循环次数了。

题外话，其实我们只需要找到最小后缀，最大循环次数可以暴力找，反正我们只需要知道结果的前 n 位和每个 B 长度是不是 1。寻找前缀的最小后缀有一些 O(n) 到 O(n\log n) 的做法，借助后缀数组或 significant suffixes 理论。这里给出一个借助 lyndon 分解的简洁 O(n) 算法，并且可以简洁地一并求出最大循环次数。

首先我们知道，最小后缀就是 lyndon 分解的最后一段，最大循环次数就是末尾相等的段数。这两个结论的证明留给读者，或可以自行查阅 lyndon 理论相关内容。

回忆 lyndon 分解的 Duval 算法。我们维护了当前前缀的一个后缀，这里暂称之为“未定串”，形如 w^k\overline w。其中 w 是一个 lyndon 串，而 \overline w 是其的前缀。新加入一个字符时，我们比较其与 w 中对应字符的大小，而决定保持这个形式，或改变其分解，或从 \overline w 的开头重新开始算法。

对于当前字符小于 w 中的对应字符时，我们把重新开始算法的过程看成是把未定串由 w^k\overline w 改为 \overline w——它是 w^k\overline w 的一个前缀。于是，我们可以使用栈记录下当前的未定串，和若算法从它开头开始，执行完它的每个位置时的未定串中 w 的长度。这样，缩短未定串的过程则是不断弹栈的过程，直到当前字符不小于 w 中的对应位置。

现在我们知道了算法从头开始执行完每个位置（即，完全不考虑之后的位置）时的未定串。若其 \overline w 为空，那么 w 即为其最小后缀，k 即为最小循环次数。否则，由 w 是 lyndon 串可知最小后缀和最大循环都不可能在第一个 w 中开头，那么我们直接把 |w| 个字符前的结果往后挪 |w| 位即可。

至此，我们完整解决了这个问题。单次 op 操作时空复杂度 O(n)，总时间复杂度 O(n\log\log n)，空间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll readint(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=1e5+5;
int n,q,b[7][maxn];
int s[maxn],s2[maxn],tp,l[maxn],l2[maxn];
void op(int* c,int* d){
    tp=0;
    for(int i=1;i<=n;i++){
        while(tp&&c[i]<s[tp-s2[tp]+1]) tp%=s2[tp];
        if(!tp||c[i]>s[tp-s2[tp]+1]) s2[tp+1]=tp+1;
        else s2[tp+1]=s2[tp];
        s[++tp]=c[i];
        if(tp%s2[tp]==0){
            l[i]=i-s2[tp]+1;
            l2[i]=i-tp+1;
        }
        else{
            l[i]=l[i-s2[tp]]+s2[tp];
            l2[i]=l2[i-s2[tp]]+s2[tp];
        }
    }
    for(int i=n;i>0;i--)
        if(i==n||l2[i+1]==i+1) l2[i]=l[i];
    int cnt=0;
    for(int i=1;i<=n&&cnt<n;i++)
        for(int j=l2[i];j<=i&&cnt<n;j++) d[++cnt]=c[j];
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    for(int i=1;i<=n;i++) b[0][i]=readint();
    for(int i=1;i<=6;i++) op(b[i-1],b[i]);
    q=readint();
    while(q--){
        int i,j;
        i=min(readint(),6ll);
        j=readint();
        printf("%d\n",b[i][j]);
    }
    #ifdef LOCAL
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}