A 好奇心宝宝

https://www.luogu.com.cn/problem/P10270?contestId=155684

题目大意：给一个网格，求两条从左上到右下的路径满足最长公共前缀最短，输出最短公共前缀长度。

做法

显然等价于找 $\{(x,y)|x+y=t\}$ 中最小的 $t$ 满足这个集合中的点的字符集大小 $>1$ 。

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
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
char st[N][N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",st[i]+1);
    }
    for(int i=1;i<=n-1+m-1;i++){
        int pre=0;
        for(int x=1;x<=i+1;x++){
            int y=i-(x-1)+1;
            if(x>=1 && y>=1 && x<=n && y<=m){
                if(!pre)pre=st[x][y];
                else if(pre!=st[x][y]){
                    printf("%d\n",i);
                    return 0;
                }
            }
        }
    }
    printf("%d\n",n+m-1);
    return 0;
}

B 漫长悄悄话

https://www.luogu.com.cn/problem/P10270?contestId=155684

题目大意：对于 $i,j$ ，贡献为 $i,j$ 前缀的翻转和后缀的 $LCP$ （四个串的 LCP ），求最大贡献。

做法

等价于找最长的奇数长度回文串满足出现了至少两次。

接下来各显神通了，可以马拉车+Hash，可以回文自动机，也可以Hash+二分。

我用了回文自动机。

Hash+二分的做法详见官方题解：https://www.luogu.com/article/sfxeve97。（需要用到本质不同的回文串只有至多 $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
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
char st[N][N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",st[i]+1);
    }
    for(int i=1;i<=n-1+m-1;i++){
        int pre=0;
        for(int x=1;x<=i+1;x++){
            int y=i-(x-1)+1;
            if(x>=1 && y>=1 && x<=n && y<=m){
                if(!pre)pre=st[x][y];
                else if(pre!=st[x][y]){
                    printf("%d\n",i);
                    return 0;
                }
            }
        }
    }
    printf("%d\n",n+m-1);
    return 0;
}

C 在四方城外

https://www.luogu.com.cn/problem/P10272?contestId=155684

题目大意：每次操作在 $S$ 后面添加 $S$ 的 mxBd ，求第 $L$ 次操作和第 $R$ 次操作之间所有操作后的字符串长度之和。

我的做法

引理 1 ：若 $ST=TS$ ，则 $S,T$ 有相同的整周期。

情况1：无Bd

若原串的 $mxBd=0$ ，则答案为 $|S|*(r-l+1)$ 。

情况2：有整周期

若原串有最小整周期 $p$ ，那么每次添加的长度必然是：$|S|-p$ ，否则一定会出现下面的情况：

那么根据引理，原串存在更小的整周期，矛盾，证毕。

情况3：无整周期但有Bd

这里给一些例子：abababababcab 、aaaaaaaba 。

为了方便下面叙述，我们设 $S_m$ 表示第 $m$ 操作后的字符串，$S_0=S$ ，然后设 $T_m=S_m-S,T_m’=(mxBd(S)+T_m)$ ，字符串 $S-T$ 定义为 $S$ 删去 $LCP(S,T)$ 。

显然，$|T_{m+1}|-|T_{m}|=|T’_{m+1}|-|T’_{m}|$ ，$|T_{m+1}|-|T_{m}|\le |T_{m+2}|-|T_{m+1}|$

接下来先说结论，整个增长过程可以分成两个部分，先是 $|T’_{m+1}|=2|T’_m|$ ，然后 $|T_{m+1}|-|T_m|$ 恒定。

定理 1 ：$|mxBd(T_{m})|\le |T’_{m}|$ 。（显然，归纳一下就行了）

因此，$|T’_{m+1}|\le 2|T’_m|$ 。

定理 2 ： $|T’_{m+1}|<2|T’_m|$ 时，则后面 $|T_{m+1}|-|T_m|$ 恒定。

证明

设 $U=mxBd(T’_{0})$ 。

$T_{m}-T_{m-1},T_{m+1}-T_m$ 是 $S$ 的一个 Bd ，显然 $T_{m}-T_{m-1}$ 是 $T_{m+1}-T_m$ 的一个 Bd 。可以得到 $T’_{0}$ 是 $T_{m+1}-T_m$ 的一个 Bd 。

根据引理 $1$ 可以得到 $U$ 是 $T_{m+1}-T_{m}$ 的最小整周期。

这个时候，可以把 $T’_{m+1},T’_{m}$ 等字符串想象成若干 $U$ 的拼接，显然 $U$ 也是 $T’_{m+1}$ 等字符串的最小整周期，否则最小整周期也是 $U$ 的整周期，与前面矛盾。

则 $|T’_{m+1}|<2|T’_m|$ ，就已经说明了 $S_{m}$ 前面只有 $\frac{|T’_{m+1}|}{|U|}$ 个 $U$ ，没有 $\frac{|T’_{m+1}|}{|U|}+1$ 个 $U$ ，若 $|T_{m+2}|-|T_{m-1}|>|T_{m+2}|-|T_{m-1}|$ ，则与 $U$ 的个数矛盾，证毕。

定理 3 ：若 $|T’_{m+1}|=2|T’_m|$ ，那么 $|T_{m+1}|-|T_{m}|<|S|$。

证明

反证法，若 $\ge n$ 。

显然 $T’_{0}$ 是 $T_{m+1}-T_{m}$ 的一个周期，即 $S_{m}$ 一个 $\ge n$ 的 Bd 的周期是 $T’_{0}$ ，注意到 $T’_{0}$ 也出现在 $S$ 的末尾，根据引理 $1$ 知道 $S$ 有整周期，矛盾，证毕。

推论： $m=\left \lfloor \log_2{|S|} \right \rfloor+1$ ，则一定有 $|T’_{m+1}|<2|T’_m|$ 。

于是就有很多种搞法了。

我的方法是直接 Kmp ，注意到长度 $\le 3n$ ，所以时间复杂度为：$O(n\log{n})$ ，空间复杂度为 : $O(n)$ 。

当然，根据上面的证明，有更加快速的搞法：求出 $U$ ，然后从左到右找至多有多少个 $U$ ，这样就可以在 $O(n)$ 的时间解决这个问题了。

注意：上面的时间复杂度都忽略了快速幂计算答案的时间。

综上，时间复杂度为：$O(n\log{n}+\log{R})$ ，空间复杂度：$O(n)$。

当然，时间复杂度可以优化到：$O(n+\log{R})$ 。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
const int N=1e6+5;
LL ksm(LL x,LL y){
    LL ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;y>>=1;
    }
    return ans;
}
char st[N*3];
int fail[N*3],n;
int gp(int len){
    fail[0]=-1;
    int now=0;
    for(int i=2;i<=len;i++){
        while(now!=-1 && st[now+1]!=st[i])now=fail[now];
        fail[i]=++now;
    }
    return fail[len];
}
int len[N];
int main(){
    scanf("%s",st+1);n=strlen(st+1);
    int d=gp(n),p=n-d;
    if(!d){
        LL l,r;scanf("%lld%lld",&l,&r);
        printf("%lld\n",(r-l+1)*n%mod);
        return 0;
    }
    if(n%p==0){
        LL l,r;scanf("%lld%lld",&l,&r);
        LL ans=ksm(2,l)*(ksm(2,r-l+1)-1+mod)%mod*(n-p)%mod;
        ans=(ans+p*(r-l+1))%mod;
        printf("%lld\n",ans);
        return 0;
    }
    int pred,m=0;
    len[m]=n;
    do{
        m++;
        len[m]=len[m-1];
        assert(len[m]+d<=n*3);
        for(int i=1;i<=d;i++)st[++len[m]]=st[i];
        pred=d;
        d=gp(len[m]);
        p=len[m]-d;
    }while(d==pred*2);
    //d is key;
    LL l,r;scanf("%lld%lld",&l,&r);
    LL ans=0;
    for(int i=l;i<=m && i<=r;i++)ans=(ans+len[i])%mod;
    if(m<r){
        l=max(l-m,1ll);
        r-=m;
        ans=(ans+len[m]*(r-l+1))%mod;
        ans=(ans+(r+l)*(r-l+1)/2%mod*d)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

感觉想出这个做法非常花时间啊。

官方题解

官方做法和我的 $O(n)$ 做法没什么区别，区别在于官方题解导出正解的路线非常短。

想想怎么更快的想出正解？

  1. 首先注意到 $S$ 有整周期（简单的）和没有整周期（不简单的）是两种情况。
  2. 其次一个必要条件是足够快的想出引理 $1$ （我的做法有提到）。
  3. 然后要有足够的观察力观察到如果设 $U$ 是 $mxBd(S)$ 的最小整周期，那么 $U$ 是这个问题的关键。
  4. 需要观察到 $U$ 是每次添加的字符串的整周期（那么显然 $U$ 是最小的整周期），否则可以证明 $mxBd(S)$ 存在更小的整周期。
  5. 设 $l$ 是从左到右 $S$ 可以匹配上的 $U$ 的个数，$r$ 是从右到左的，如果 $(l+r-1)*|U|\ge |S|$ ，则可以说明 $S$ 有最小整周期，矛盾。
  6. 根据 $4,5$ 就可以得到 $O(n)$ 做法，也可以根据至多 $O(\log)$ 后增速固定，且在这之前字符串长度至多乘 $3$ 倍的性质，想出更加好写的 $O(n\log{n})$ 做法。

观察上面过程，在第 $3$ 步之后对我而言比较自然，也就是想要更快的做出这题，更快的想出第 $2,3$ 步是关键。

D 大娱乐至上

题目链接：https://www.luogu.com.cn/problem/P10273?contestId=155684

题目大意：给你一个字符串，给一堆区间代表子串，问你每个区间能不能在只改变原串一个字母的情况下，使原本给出的小于它的子串现在大于等于它了。

我的做法

我考场的第一想法是后缀数组，但非常可惜的是太过答辩，以至于我根本没有时间在考场上品鉴完。

一个简单的思路是：要么改变这个子串，变小一个字母。要么让其余所有原本小于它的给定子串变大，变大一个字母。

基础实现思路：从小到大遍历子串，然后讨论当前这个子串是否可行，如果有多个相同的子串，则同时进行查询即可（即全部询问完后再执行相应的修改操作）。

然后就可以开始讨论了：

不妨设现在考虑的是 $[l_i, r_i]$ ，下面不加说明时，都仅考虑原本小于它的子串 $[l_j, r_j]$ ，设 $lcp(x,y)$ 表示 $x,y$ 后缀的最长公共前缀，同时下面提到的子串都指题目给定的子串。

变小一个字母（一个基本性质是所有子串只可能变小不可能变大）：

  1. 显然，如果要让 $[l_i, r_i]$ 小于等于 $[l_j,r_j]$ ，设 $len = min(lcp(l_i, l_j), r_j - l_j + 1, r_i - l_i + 1)$ ，则显然改的字符必须落在 $[l_i, l_i + len - 1]$ 。
  2. 同时如果改的字符同时落在 $[l_i, r_i]$ 和 $[l_j, r_j]$ ，那么显然必须有：$l_i > l_j$ ，即如果有 $l_j \ge l_i$ 的话，修改的位置不能在 $[l_i,r_i]\cap [l_j,r_j]$ ，同时根据上一条可以知道，修改的位置不可能在 $l_j$ 之后，即落点只能落在 $[l_i, l_j - 1]$ 。（可以发现，找到右边最近的 $l_j$ 给个约束就行了，可以用单调栈预处理达到 $O(n)$ ）

这样就可以得到修改的位置必须落在的区间，而且根据上面的讨论，不难发现只要落在这个区间，直接改到 $<a$ 就可以符合要求了，即这个区间有可改的位置是改小可行的充要条件。

现在问题是，第一点怎么实现？

假设小于等于 $[l_i,r_i]$ 的子串（包括自己）中 $l$ 后缀 rank 最大为 $k$ ，同时所有给定的字符串中 rank 最小的 $l$ 的 rk 为 $smallrk$ 。

那么第一点的限制可以写成 $min(lcp(sa[smallrk],l),r_{j}-l_{j}+1(\forall j : [l_j,r_j]\le [l_i,r_i]))$ ，这样就可以维护了，具体实现中，还可以将 $lcp(sa[smallrk],l)$ 换成 $lcp(sa[k],l)$ ，因为显然 $lcp(sa[smallrk],sa[k])\ge min(r_{j}-l_{j}+1(\forall j : [l_j,r_j]\le [l_i,r_i]))$ 。

可以在询问的过程中一起维护，时间复杂度 $O(n)$ 。

变大一个字母（一个基本性质是所有子串只可能变大不可能变小）：

  1. 需要让这个位置落在所有 $[l_j,r_j]$ $([l_j,r_j]<[l_i,r_i])$ 。（很容易 $O(n)$ 处理）
  2. 如果要让 $[l_i, r_i]$ 小于等于 $[l_j,r_j]$ ，则显然改的字符必须落在 $[l_j, l_j + lcp(l_i, l_j)]$ 。
  3. 如果要让 $[l_i, r_i]$ 小于等于 $[l_j,r_j]$ ，则显然改的字符必须落在 $[l_j, l_j + (r_i - l_i + 1) - 1]$ 。（很容易 $O(n)$ 处理）
  4. 若 $\exists j : l_j \le l_i ,[l_j,r_j] <[l_i,r_i]$ ，则显然修改位置不能落在 $[l_i,r_i]$ ，否则 $[l_i,r_i]$ 的增大程度大于 $[l_j,r_j]$ 。（很容易 $O(n)$ 处理）

这样就可以得到修改的位置必须落在的区间，而且根据上面的讨论，不难发现只要落在这个区间，直接改到 $>z$ 就可以符合要求了，即这个区间有可改的位置是改大可行的充要条件。

现在问题是，第二点怎么实现？毕竟 $rk[l_i]$ 可以跳上跳下的 ，因此维护 $lcp(l_i,l_j)$ 是个很困难的事情。

假设大于等于 $[l_i,r_i]$ 的子串（包括自己）中 $l$ 后缀 rank 最大为 $k$ 。

那么实际上只需要考虑 $j:[l_j,r_j]<[l_i,r_i],rk(l_j)<k$ ，且 $lcp$ 只需要考虑 $lcp(l_j,sa[k])$ ，原因是这样子改的影响一定可以被其余三点消掉。（一个基本的事实是：若 $rk[l_i]\ge rk[l_j]$，但 $[l_i,r_i]\le[l_j,r_j]$ ，那么 $[l_i,r_i]$ 一定是 $[l_j,r_j]$ 的前缀）

这样子的好处是可以用一个栈轻松实现这个过程。

综上，在对子串排序后，所有的讨论都可以在线性的时间解决。

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

空间复杂度：$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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 5;
const int SN = 20;
int n,m;
char ss[N],ch[N];
char ans[N];
set<int> chp;//change pos
PII getcp(int l,int r){
    PII x = {n+1, n+1};
    if(l>r)return x;
    auto tmp = chp.lower_bound(l);
    if(tmp != chp.end()) x.first = *tmp;
    tmp = chp.upper_bound(r);
    if(tmp != chp.begin()){
        tmp--;
        x.second = *tmp;
    }
    if(x.first > r) x.first = n + 1;
    if(x.second < l) x.second = n + 1;
    return x;
}
namespace SA{
    int cc[N],sa[N],xx[N],yy[N],top,V;
    int rk[N],height[N],h[N];
    void getsa(){
        //need clear : height,h
        V=26;memset(cc+1,0,V<<2);
        for(int i=1;i<=n;i++)cc[xx[i]=ss[i]-'a'+1]++;
        for(int i=1;i<=V;i++)cc[i]+=cc[i-1];
        for(int i=n;i>=1;i--)sa[cc[xx[i]]--]=i;
        for(int k=1;k<n;k<<=1){
            top=0;for(int i=n;i>n-k;i--)yy[++top]=i;
            for(int i=1;i<=n;i++){
                if(sa[i]>k)yy[++top]=sa[i]-k;
            }
            memset(cc+1,0,V<<2);
            for(int i=1;i<=n;i++)cc[xx[i]]++;
            for(int i=1;i<=V;i++)cc[i]+=cc[i-1];
            for(int i=n;i>=1;i--)sa[cc[xx[yy[i]]]--]=yy[i];
            swap(xx,yy);
            V=xx[sa[1]]=1;for(int i=2;i<=n;i++)xx[sa[i]]=V+=!(sa[i]+k<=n && sa[i-1]+k<=n && yy[sa[i]]==yy[sa[i-1]] && yy[sa[i]+k]==yy[sa[i-1]+k]);
            if(V==n)break;
        }
        
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        int now=0;ss[n+1]='\0';
        for(int i=1;i<=n;i++){
            if(now)now--;
            if(rk[i]==1)continue;
            while(ss[i+now]==ss[sa[rk[i]-1]+now])now++;
            h[i]=now;height[rk[i]]=now;
        }
    }
    int rmq[SN][N];
    void init_rmq(){
        for(int i=1;i<=n;i++)rmq[0][i]=height[i];
        for(int i=1;i<=19;i++){
            for(int j=n-(1<<i)+1;j>=1;j--)rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
        }
    }
    int getrmq(int x,int y){
        int z=__lg(y-x+1);
        return min(rmq[z][x],rmq[z][y-(1<<z)+1]);
    }
    int getlcp(int x,int y){
        if(x==y)return n-x+1;
        x=rk[x];y=rk[y];
        if(x>y)swap(x,y);
        return getrmq(x+1,y);
    }
}
using SA::getsa;
using SA::init_rmq;
using SA::getlcp;
using SA::height;
using SA::sa;
using SA::rk;

int ql[N],qr[N],qlen[N],id[N];
bool cmp(int x, int y){//x<y;
    int k=getlcp(ql[x], ql[y]);
    if(qlen[x] <= k || qlen[y] <= k) return qlen[x] < qlen[y];
    else return ss[ql[x] + k] < ss[ql[y] + k];
}
//small square
int smallrk,minlen;
set<int> banp;//ban pos

//big square
int minl, maxl;
PII stk[N];int top;
int maxrk,rp;
multiset<int> querypos;
bool v[N];
int main(){
    cin >> n >> m;
    cin >> ss+1 >> ch+1;
    getsa();
    init_rmq();
    for(int i = 1; i <= n; i++){
        if(ch[i] == '1') chp.insert(i);
    }
    for(int i = 1; i <= m; i++){
        cin >> ql[i] >> qr[i];
        qlen[i] = qr[i] - ql[i] + 1;
        id[i] = i;
        ans[i] = '0';
        querypos.insert(rk[ql[i]]);
        v[ql[i]] = 1;
    }
    sort(id + 1, id + m +1, cmp);
    
    //small init
    minlen = smallrk = n;
    for(int i = 1; i <= m; i++)smallrk = min(smallrk, rk[ql[i]]);
    //max init
    maxrk = maxl = 1;
    minl = n + 1;
    rp = n;
    for(int tl = 1; tl <= m; tl++){
        int tr = tl;
        while(tr < m && getlcp(ql[id[tl]], ql[id[tr + 1]]) >= qlen[id[tl]] &&
            getlcp(ql[id[tl]], ql[id[tr + 1]]) >= qlen[id[tr + 1]] && qlen[id[tl]] == qlen[id[tr + 1]]) tr++;
        if(tl == 1){
            for(int i = tl; i <= tr; i++) ans[id[i]] = '1';
        }
        for(int i = tl; i <= tr; i++){
            //small change
            int x = id[i];
            int l = ql[x], r = qr[x];
            while(rk[l] > smallrk){
                smallrk++;
                minlen = min(minlen, height[smallrk] + 1);
            }
            minlen = min(minlen, qlen[x]);
            //big change
            while((*querypos.begin()) > maxrk){

                if(v[sa[maxrk]]){
                    int pos = sa[maxrk];
                    stk[++top] = {pos, n - pos + 1};
                }

                maxrk++;
                int tmp = height[maxrk] + 1;
                if(top && stk[top].second > tmp){
                    PII y = stk[top];
                    while(top && stk[top].second >= tmp){
                        y.first = min(y.first, stk[top].first);
                        top--;
                    }
                    y.second = tmp;
                    stk[++top] = y;

                    rp = min(rp, y.first + y.second - 1);
                }
            }
        }
        for(int i = tl; i <= tr; i++){
            int x = id[i];
            int l = ql[x], r = qr[x];
            //small query
            if(minlen){
                int rban= n + 1;
                auto tmp=banp.lower_bound(l);
                if(tmp != banp.end()) rban = *tmp;
                auto [al, ar] = getcp(l, min(rban - 1, l + minlen - 1));
                if(al != n + 1) ans[x] = '1';
            }
            //big query
            if(maxl <= min(rp, minl + qlen[x] - 1)){
                auto [al, ar] = getcp(maxl, min(rp, minl + qlen[x] - 1));
                if(al<l) ans[x] = '1';
                if(minl > l && ar != n + 1) ans[x] = '1';
            }
        }
        for(int i = tl; i <= tr; i++){
            int x = id[i];
            int l = ql[x], r = qr[x];
            //small change
            banp.insert(l);
            //big change
            querypos.erase(querypos.find(rk[l]));
            
            minl = min(minl, l);
            maxl = max(maxl, l);

            rp = min(rp, r);
        }
        tl = tr;
    }

    cout << ans + 1 << '\n';
    return 0;
}

能不能再快一点？空间能不能再小一点？

答案是可以的，首先后缀数组换成 SA-IS ，但即使换成 $O(n)-O(1)$ RMQ 排序也要 $O(n\log{n})$ ，如何处理呢？

注意到一个事情，排序的时候只关注子串是什么，而不关注子串的位置，因此只要我们能给每一个子串，找到最小的以该子串为前缀的后缀即可，做法也很简单：

将 height 从大到小跑，然后用并查集维护连接起来的一块，然后每次把一个子串送到所在连通块中排名最小的后缀即可。

这样就能在 $O(n\alpha(n))$ 时间排序完毕，再算上 $O(n)$ 的讨论，理论上能做到的最优复杂度：

时间复杂度：$O(n\alpha(n)))$

空间复杂度：$O(n)$