对应比赛：The 2024 ICPC Asia Hangzhou Regional Contest

比赛链接：https://qoj.ac/contest/1893

总结：我打的一坨。

开局队友神勇，过了 A,K ，一开始 M 很快意识到一层层搜，只要有解，时间复杂度是 $O(n\log{V})$ 的，无解中途退出就行了，但是不知道怎么处理限制，然后去问队长，队长也不知道，但后面发现可以是 $n*240$ ，其中 $240$ 是 $10^9$ 最多的因子个数，遂流汗，这么出题的。不过这时便初见端倪。

后面队友在写 F ，队长告诉我 H 做法，我再看了 E ，在队友过 F 后我去把这两题写了。

后面开 B ，觉得并不是一个简单题，丢给了数据结构大师。队长告诉了我 J 的大致做法（埋下伏笔），我去写 J 。中途听到 Imakf 说 B 不是线段树就行了吗，虽然浅浅意识到正解应该不是简单的线段树，但是因为在机上，我就什么都没说了，如果在机下的话还是应该和他讨论一下，数据结构题假掉比较麻烦，后面也确实假了一次。

然后伏笔暴雷了，我 J 一开始不想写 $2^mm$ 的状压，就是喜欢复杂度小的做法，所以写的 DFS ，但是好巧不巧的是，这个做法有一个细节想错了，所以是不对的，在写了对拍后，终于在 2:30 意识到问题所在，但因为需要加的部分和原先代码的相性相当差，于是在修正代码的时候就有一种强烈的赤石感，而且由于修正部分有一个高维前缀和，所以最后复杂度还是 $O(2^mm)$，唐完了。所以以后这种题目如果有复杂度大但能过，而且更加好写的做法还是写这种，别为了那一点复杂度专门写个 DFS 恶心自己，大不了 T 了再换，还能顺便攻击一下出题人。如果 DFS 的做法写久了，就只能攻击自己了，而且攻击者大概率不止自己一个人。

终于，1:30 开写，在 3:00 AC，成功将队伍拖向深渊。

然后期间队友会了 B,I ，开写，先过了 I ，队友上去写 B ，在队友写 B 的时候，队长告诉了我 D 的题意和 G 的做法。

我在想了一会 D 后，没什么具象的做法。在队友过了 B 后，我感到大事不妙，G 这坨屎大概得是我吃了。怀着对石的天然厌恶，而且也确实没想好怎么写，我战战兢兢的问了句这个谁写，队长给出了充足的理由让我去写：你已经想了会 D ，没有想出什么东西，所以先让 Imakf 想想。

于是我开了这坨屎。不出所料，卡的我精神恍惚，最终花了一个半小时过了，队友 D 也卡的精神恍惚，无法战胜。

M

做法

首先看最小的数字，答案加上最小的数字肯定是其余数字与最小数字差值的最大公约数的因子。

然后每个最小的数字将序列分成若干段，每一段接着做，这样会得到 $n$ 个限制，而且可以知道的是，如果有解，则每个分支的深度至多为 $\log{n}$ ，而 $10^9$ 的因子个数至多为 $240$ ，所以只需要把第一个限制的所有可能答案找到，后面不断 check 就行了。

时间复杂度：$O(n(\log{n}+\log{V}+240)+\sqrt{V})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
const int N = 5e4 + 5;
int gcd(int x, int y){return !x ? y : gcd(y % x, x);}
int n, k, a[N];
vector<int> f; bool type = 0;
void push(int x){
    if(x <= k && x >= 1) f.push_back(x);
}
void solve(int l, int r){
    if(l > r) return ;
    if(type && f.empty()) return ;
    // debug("%d %d : \n", l, r);
    // debug("type = %d\n", type);
    // for(auto x : f) debug("%d ", x);
    // debug("\n");
    int minval = 1e9 + 1, d = 0;
    for(int i = l; i <= r; i++){
        minval = min(minval, a[i]);
    }
    vector<int> pos; pos.push_back(l - 1);
    for(int i = l; i <= r; i++){
        d = gcd(d, a[i] - minval);
        if(a[i] == minval) pos.push_back(i);
    }
    // debug("d = %d minval = %d\n", d, minval);
    pos.push_back(r + 1);
    if(!d) return ;
    else{
        if(!type){
            type = 1;
            for(int i = 2; i * i <= d; i++){
                if(d % i == 0){
                    push(i - minval);
                    if(i * i != d) push(d / i - minval);
                }
            }
            push(d - minval);
        }
        else{
            vector<int> tmp;
            swap(tmp, f);
            for(auto x : tmp){
                if(d % (minval + x) == 0) push(x);
            }
        }
    }
    for(int i = 1; i < pos.size(); i++){
        solve(pos[i - 1] + 1, pos[i] - 1);
    }
}
int main(){
    int T;
    cin >> T;
    while(T--){
        type = 0;
        vector<int> tmp;
        swap(tmp, f);
        cin >> n >> k;
        for(int i = 1; i <= n; i++) cin >> a[i];
        solve(1, n);
        if(!type){
            cout << k << " " << 1ll * k * (k + 1) / 2 << "\n";
        }
        else{
            LL ans = 0ll;
            for(auto x : f) ans += x;
            cout << f.size() << " " << ans << "\n";
        }
    }
    
    return 0;
}

M

做法

由于所有人都是往上走的，不妨假设有人要到最高层，那么答案就是运输距离加上 $f$ 层往上没有被覆盖的层数。

这显然是下界，而构造也很简单，先不断的往上走，走到最高层，然后按照 $r$ 从大到小排序，一个个人运输就行了。

时间复杂度：$O(n\log{n})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 5;
int n, f;
struct node{
    int l, r, id;
}a[N];
void work(){
    cin >> n >> f;
    LL ans = 0ll;
    for(int i = 1; i <= n; i++){
        cin >> a[i].l >> a[i].r;
        ans += a[i].r - a[i].l;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, [](node x, node y){return x.l < y.l;});
    vector<int> sol, tmp;
    for(int i = 1; i <= n; i++){
        if(a[i].r > f) sol.push_back(a[i].id);
        else tmp.push_back(a[i].id);
        ans += max(0, a[i].l - f);
        f = max(a[i].r, f);
    }
    cout << ans << "\n";
    for(auto x : sol) cout << x << " ";
    reverse(tmp.begin(), tmp.end());
    for(auto x : tmp) cout << x << " ";
    cout << "\n";
}
int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        work();
    }
    return 0;
}

H

做法

讨论一下就行了，如果最长链只有一条，全挂在最长链顶端，否则，最短链得 $\le$ 最长链链长 $-2$ ，否则显然无解。

时间复杂度：$O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
int n, k, a[N];
int p[N];
void print(){
    for(int i = 1; i <= n; i++) cout << p[i] << " ";
    cout << "\n";
}
int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n >> k;
        vector<PII> e;
        for(int i = 1; i <= k; i++){
            int l, r;
            cin >> l >> r;
            for(int j = l + 1; j <= r; j++) p[j] = j - 1;
            e.push_back({r - l + 1, l});
        }
        sort(e.begin(), e.end());
        reverse(e.begin(), e.end());
        if(e.size() > 1 && e[0].first == e[1].first){
            if(e[0].first - e.back().first <= 1) cout << "IMPOSSIBLE\n";
            else{
                for(auto [len, rt] : e){
                    if(len >= e[0].first - 1) p[rt] = e[0].second;
                    else p[rt] = e[0].second + 1;
                }
                p[e[0].second] = 0;
                print();
            }
        }
        else{
            for(auto [len, rt] : e) p[rt] = e[0].second;
            p[e[0].second] = 0;
            print();
        }
    }
    return 0;
}

J

tag：状压dp

做法

考虑左边每种数字是否出现，有 $2^{m}$ 种。

考虑一组限制 $(a,b)$ ，如果左边没有 $a$ ，就会要求左边有 $b$ ，右边有 $a$ ，反之亦然，但是这样的限制不足以合法，因为注意到如果左边有 $a,b$ ，对右边没有限制，或者说有一个很难处理的限制：$a,b$ 至少出现一个。但是其实 $a,b$ 至少出现一个的限制无论左边是什么，右边都有这个限制，因此先用状压 dp 先处理出右边所有的合法情况，在用高维前缀和统计贡献就行了。

时间复杂度：$O(m2^m)$ 。

B

tag：线段树

做法

首先如果拆位了，那么基本上都会被卡到 $O(n\log{n}\log{V})$ 。

所以要压位，状压处理。一个关键是，我们其实只要知道被删除的位置是哪个，处理出剩下的 and 和是简单的。

又发现，只要处理出是哪个 bit 恰好缺一个，则处理出被删除的位置是哪个是显然的，到这就呼之欲出了。

就是维护三个状态，删除了 $0$ / $1$ / $\ge 2$ 个的 bit ，然后合并是简单的，随便维护一下就行了。

时间复杂度：$O(n\log{n}+n\log{V})$ 。

看了下，队友也是这个思路。

G

tag：基环树

做法

做法队友提出的，写起来挺石的。

大体思路就是，先处理出从环上一点出发每个颜色的答案，存在一个 set 里面，然后每次新增一个点，对应颜色见到第 $k$ 次的位置会向前移动，移动到哪个位置是好处理的，然后撤销也是好撤销的，然后就做完了。

时间复杂度：$O(n\log{n})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 2e5 + 5;
int a[N], t[N], n, k;

vector<int> son[N]; int v[N];
int col[N];
vector<int> cpos[N]; int pre[N], pos[N], clen;
int dis(int x, int y){//x -> y
    if(y <= x) y += clen;
    return y - x;
}

PLI rep[N];
set<PLI> s;
vector<int> peo;
vector<PLI> stk[N];
int cop[N], dep[N];//下面的坐标
vector<int> cc[N];

LL ans;

void dfs(int x, int type){
    peo.push_back(x);
    cc[t[x]].push_back(x);
    cop[x] = cc[t[x]].size() - 1;
    if(!rep[t[x]].second){
        if(cop[x] == k - 1){
            int y = cc[t[x]][0];
            s.insert(rep[t[x]] = {1ll * dep[y], y});
        }
    }
    else{
        auto [ti, y] = rep[t[x]];
        stk[t[x]].push_back(rep[t[x]]);
        if(ti >= 0){
            if(ti - dis(pos[pre[y]], pos[y]) >= 0) s.insert(rep[t[x]] = {ti - dis(pos[pre[y]], pos[y]), pre[y]});
            else{
                int z = cc[t[x]][0];
                // assert(false);
                s.insert(rep[t[x]] = {1ll * dep[z], z});
            }
        }
        else{
            int z = cc[t[x]][cop[y] + 1];
            s.insert(rep[t[x]] = {1ll * dep[z], z});
        }
    }
    for(auto y : son[x]){
        if(v[y] == 2) continue;
        dep[y] = dep[x] - 1;
        dfs(y, 0);
    }
    // debug("ans[%d] = %d\n", x, (*s.begin()).second);
    assert(!s.empty());
    ans += 1ll * x * t[(*s.begin()).second];
    if(!type){
        cc[t[x]].pop_back();
        s.erase(rep[t[x]]);
        rep[t[x]] = {0ll, 0};
        if(!stk[t[x]].empty()){
            s.insert(rep[t[x]] = stk[t[x]].back());
            stk[t[x]].pop_back();
        }
    }
}

void solve(int rt){
    while(!v[rt]){
        v[rt] = 1;
        rt = a[rt];
    }
    vector<int> cir;
    while(v[rt] != 2){
        v[rt] = 2;
        cir.push_back(rt);
        pos[rt] = cir.size() - 1;
        cpos[t[rt]].push_back(rt);
        rt = a[rt];
    }
    clen = cir.size();
    for(int i = 0; i < cir.size() * 2; i++){
        int x = cir[i % cir.size()];
        if(col[t[x]] && !pre[x]) pre[x] = col[t[x]];
        col[t[x]] = x;
    }
    // debug("circle : ");
    // for(auto x : cir) debug("%d ", x);
    // debug("\n");
    // for(int i = 0; i < clen; i++) debug("pre[%d] = %d\n", cir[i], pre[cir[i]]);
    for(auto x : cir){
        if(x == cpos[t[x]][0]){
            int y = (k - 1) % cpos[t[x]].size();
            int T = (k - 1) / cpos[t[x]].size();
            int z = cpos[t[x]][y];
            s.insert(rep[t[x]] = {1ll * T * clen + pos[z], z});
        }
    }
    // for(int j = 1; j <= n; j++){
    //     if(rep[j].second) debug("col = %d time = %lld pos = %d\n", j, rep[j].first, rep[j].second);
    // }
    for(int i = clen - 1; i >= 0; i--){
        // debug("rt = %d : \n", cir[i]);
        // for(int j = 1; j <= n; j++){
        //     if(rep[j].second) debug("col = %d time = %lld pos = %d\n", j, rep[j].first, rep[j].second);
        // }
        dep[cir[i]] = i - clen;
        dfs(cir[i], 1);
    }
    for(auto x : peo){
        col[t[x]] = 0;
        cpos[t[x]].clear();
        rep[t[x]] = {0ll, 0};
        stk[t[x]].clear();
        cop[x] = dep[x] = 0;
        cc[t[x]].clear();
        v[x] = 2;
    }
    peo.clear(); s.clear();
}
int main(){ 
    // cin.sync_with_stdio(false);
    // cin.tie(0);
    int T; cin >> T;
    while(T--){
        cin >> n >> k;
        for(int i = 1; i <= n; i++) cin >> t[i];
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            son[a[i]].push_back(i);
        }
        for(int i = 1; i <= n; i++){
            if(!v[i]) solve(i);
        }
        cout << ans << "\n";
        ans = 0;
        for(int i = 1; i <= n; i++){
            son[i].clear();
            v[i] = pre[i] = pos[i] = cop[i] = dep[i] = 0;
        }
    }
    return 0;
}

D

tag：Lyndon

做法一

注：字符串的严格不等号为去掉前缀的情况。

首先对串进行 Lyndon 分解，现在证明，Lyndon 串一定一起出现在一个串中。

先证明一个引理：

一个 Lyndon 串的答案就是其本身

递归证明，先假设更短的 Lyndon 串是对的，现在可以知道，一个 Lyndon 串可以写成 $AA…AA’$ 的形式，其中 $A’$ 是 $A$ 的一个前缀加上一个大字母，$A,A’$ 是 Lyndon 串 。

所以 $A,A’$ 如果拆成两个串，一定会有一个串严格大于原本的串，用这个可以证明所有 $A$ 或者 $A’$ 都应该完整存在，否则一定不优，进而证明这个 Lyndon 串自身就是最好的串。

在证明完这个后，就可以证明以下定理：

现在已经有个串 $S

设 $L=AA…AA’$，后续的串为 $P$ 。根据归纳，可以知道每个 $A$ 和 $A’$ 都是完整放置的，注意这里的归纳比较神秘，$S,T$ 是可以变的，但因为还是有限归纳，所以正确性显然。

然后，如果 $S=T$ 或者 $S,T$ 之间已经有严格的大小关系，则显然正确，所以不妨设 $T$ 是 $S$ 的真前缀，或者不妨设 $T$ 为空串。

现在讨论为啥是 $AA…AA’$ 放置。

如果 $A’$ 放置在 $S$ 后面，则显然 $S$ 后面直接放置 $L+P$，答案显然更小，所以反例只可能是 A’ 在另一边。

所以讨论 $A’$ 放在 $T$ 后面且有 $A$ 放在 $S$ 的情况，不妨设新的串为 $S’,T’$，设 $T’’=S+L$ 。

如果 $S$ 严格大于 $T’’$ ，又显然 $max(S’,T’)\ge S$ ，只需要把 $P$ 放置在 $T’’$ 后面就得到更优答案。

如果 $T’’$ 是 $S$ 前缀，则有 $T’$ 严格大于 $S,T’’$ ，所以也显然不优。

如果 $T’’>S$ ，则显然 $max(T’’+P,S)=T’’+P<T’<=max(S’,T’)$ ，所以也显然不优。

综上，$L$ 一定完整存在。

证毕。

有了这个结论，就知道 Lyndon 分解中每个 Lyndon 串完整存在，那做法就显然了，设 $L_{i}$ 为第 $i$ 个 Lyndon 串。

将 $L_{2i-1}$ 加入到答案中，如果 $L_{2i-1}=L_{2i}$ 则增大 $i$ 并继续，否则停下来。

至于原因，就是 Lyndon 分解后的串可以根据大小当成单个字符来对待，对于一个非递增的序列，答案是显然的。

时间复杂度：$O(n)$ 。

从上面的证明，可以看到 Lyndon 串有相当良好的递归性质，如果当思考字符串问题的时候，发现这个字符串的答案有一种近似递归的结构，就可以考虑一下答案的结构是不是和 Lyndon 分解有关，血的教训。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, m, a[N], b[N];
int *ls[N];
vector<int> ans;
vector<vector<int>> lyn;
void add(vector<int> x){
    for(auto y : x) ans.push_back(y);
}
int main(){
    int T;
    cin >> T;
    while(T--){
        ans.clear(); lyn.clear();
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            ls[i] = &a[i];
        }
        sort(ls + 1, ls + n + 1, [](int *x, int *y){return (*x) < (*y);});
        int pre = m = 0;
        for(int i = 1; i <= n; i++){
            if((*ls[i]) != pre) pre = (*ls[i]), m++, b[m] = pre;
            (*ls[i]) = m;
        }
        int i = 1;
        while(i <= n){
            int j = i + 1, k = i;
            while(j <= n && a[k] <= a[j]){
                if(a[k] < a[j]) k = i;
                else k++;
                j++;
            }
            while(i <= k){
                vector<int> tmp;
                for(int t = i; t < i + j - k; t++) tmp.push_back(a[t]);
                lyn.push_back(tmp);
                i += j - k;
            }
            //[i,i+j-k)即为对应的Lyndon分解 
        }
        // for(auto v : lyn){
        //     for(auto x : v) cout << x << " ";
        //     cout << "\n";
        // }
        reverse(lyn.begin(), lyn.end());
        while(!lyn.empty()){
            if(lyn.size() == 1){
                add(lyn.back());
                break;
            }
            auto x = lyn.back(); lyn.pop_back();
            auto y = lyn.back(); lyn.pop_back();
            add(x);
            if(x != y) break;
        }
        cout << ans.size() << "\n";
        for(auto x : ans) cout << b[x] << " ";
        cout << "\n";
    }
    return 0;
}

战败记录：

赛时想到哪一步了？

赛时的思路是，按照前缀最小值不同分段，原因是感觉上第一次出现小于第一个数字的位置会很特殊，所以这样子分了。

然后先对第一段进行讨论（至于后面的段如何处理等到后面再说），不妨设第一段的开头为 $1$ ，当时的想法是，对这一段按照若干个 $1$ 接一个比 $1$ 大的数字分段。

例如：$1,1,2,3,1,1,2,1,1$ 分成 $1,1,2$ 、$3$ 、$1,1,2$ 、$1$ 、$1$ 。

手玩一下会发现，$1,1,2$ 应该完整的存在于一段中，即这样一段一定会完整的存在于一段中，然后后面的段如果小于第一段，直接就结束了，大于的话，就一定是完整的接在后面，等于的情况没时间讨论了。

但大体感觉是这些段会完整的存在。

现在讨论一下我有可能能以什么路线想出这道题目？

直接想出 Lyndon 不太可能，毕竟这个角度虽然有递归结构，但是我当时并没有体会到 Lyndon 也有递归结构，而且这个结构跟 Lyndon 的递归结构有点区别，所以能否通过别的路线想出一个本质一样的做法呢？

第一种可能性是接着手玩，直接讨论出类似 Lyndon 串的做法，事实上讨论等于的情况会发现会维护类似周期的东西，等到破除周期的时候才能确定具体放法，重复下去就能得到做法（实际上这就是构造 Lyndon 分解的过程）。这个可能性在我做 AGC043C 亦有记载，我至今都不知道当时怎么在没看出 SG 的情况下直接想出结论的。不过直接这样子写代码可能会写的很丑，而且对讨论功力的要求比较高，就算真能讨论明白，也要花大量的时间，基本不可能在赛时完成，于是寻找另外一种可能性。

第二种可能性是另外一种方式去递归定义 Lyndon 串，这首先得注意到一个事情：

按照前缀最大值分段，则每一段实际上是独立的。详细说明就是，不妨设最开头是 $2$ ，然后找到第一个 $1$ 的位置，不妨设这个位置以前的字符串的分法为 $S,T$ ，如果 $S=T$ ，则显然答案是 $S+$ 后面的分法，如果 $S≠T$ ，则只要把后面的字符串接在 $min(S,T)$ 后面，就会得到答案显然是 $max(S,T)$ 了。

因此我们只关心每一段中相等和不相等的最好分法。而这个时候不需要观察力也会自然的想，会不会只关心最好分法，然后加点小小的讨论就可以证明了。

换句话说，我们实际上只关心每一段的最优答案。这也就呼应了前面那句 “ 感觉上第一次出现小于第一个数字的位置会很特殊 ” 的话，实际上每一次前缀最小值变小的位置都是特殊的，只可惜赛时虽然有这个感觉，也按照这个分段讨论了，赛后也觉得既然有了这个感觉，想出这个结论也应该是自然的，可惜赛时并没有想出来这个结论，十分可惜。

在想出这个结论后，对于每一段，不妨就第一段而言吧（首字母为 $1$ ），如果讨论时能够注意到讨论的对象都不是单个的数字，而是 $1,1,1,1,x$ 的段，就应该自然的想到能不能将这些段按照字典序关系变成单个数字，然后等效成一个全新的问题。

而要做到这点，需要满足两个很重要的条件：

  1. 每个数字串在答案中一定完整存在（证明不在赘述）。
  2. 新的数字串的序关系和原串等价。

由于每个串实际上都能写成二元组的形式，即 $(c,x)$ ，$c$ 个 $1$ ，最后的非 $1$ 数字是 $x$ ，没有就是 $0$ ，但是突然发现，第二个条件是不能满足的。

例如：1 + 2 = 12 ，但在转换过后这个 $=$ 会变成 $<$ ，这是我们不想看到的事情，但是如果注意力高一点，可以注意到原段中 1 + 2 不会出现在子序列中，因为这一段中 1 后面除了 1 没有别的字符了。

因此，这启示我们，有没有可能其实还要把末尾的 1 给分出去，用跟上面类似的讨论可以得到，答案是基于去掉末尾的 1 的字符串的，也就是我们可以忽略末尾的 1 ，这样这个条件就对了。

于是，我们可以不断地重复这个过程，这样就已经得到了一个 $O(n^2\log{n})$ 的递归做法。上面的过程每一步都比较自然，因此这个做法是可能能想出来的。

而且，我们来研究这个过程，会得到 Lyndon 串的另外一种递归定义方式，就是上面这种，至于为什么是 Lyndon 这里就不过多证明了，感觉不难。但上面这种定义方式并不优美，可以发现，我们实际上没必要分段，末尾的 1 也没必要去掉，前者的原因是可以发现，前缀最大值减少的位置在这个递归过程一直充当分割线的位置，所以无需担心，后者的原因正如上面提到的，不会出现 1 + 2 的情况。这样虽然优雅，但是不够自然，但从结果来看，这才是我们想要的结论。

这样，我们就得到了一个全程和 Lyndon 的定义关系不大的递归定义 Lyndon 的方法，更加说明了一个事情 ：Lyndon 有相当良好的递归性质。所以字符串的答案有递归结构，就很有可能和 Lyndon 有关。

总结一下，我要想出这个题目可能需要以下关键：

  1. 在注意到答案有递归结构的时候思考答案的结构是否和 Lyndon 有关。
  2. 在讨论的时候注意到本质是在讨论 1,1,1,x 的数字串，然后尝试缩串。

第一点要求对 Lyndon 串有熟练度，而第二点则要求在想题目的时候，时刻思考现在的讨论本质是在讨论什么，尝试通过现有的蛛丝马迹逐步抽象出问题的本质。

当然，可能有人会说，我能找到本质那问题不就做完了，难不就难在找本质，对此，我的回答是：

  1. 这里并不要求一下直接找到原题的本质，而是找到现有思路的本质，难度会小很多，而且也并非一下子找出来，而是不断地更新对本质地认识，不断接近真正的本质，最终做出题目。

  2. 做题目的过程要有找本质的意识，虽然没有也能做题，当然可以以各种方式做出题目后，知道做法后说一句这就是这道题目的本质啊然后投身下一道题目。但是这个思考方法是我现在认为比较高效的思考方法，不仅在过程中能让你反复审视现有的想法，减少不必要的弯路、失误，循序渐进；也能在做完题目后，更加清晰地意识到这道题目地本质和价值，不只是做了一道题目。

    而且我一直在思考一个事情，什么做题方法能摆脱应试的标签，而且并不大而空。什么做题方法能够真正意义上让人思维获得新生，而不是只是单纯的经验积累，遇到新怪直接 GG 。这个方法就是我目前的答案，至于真正效果如何 敬请期待以后的博客。

虽然上面的讨论确实有先射箭后画靶的嫌疑，但是这里只是讨论如果我要自然的想出这道题目，最有可能的路线是什么，所以也就无所谓了。