题解 洛谷P7361 「JZOI-1」拜神

发表于 更新于 分类于 本文字数： 6k 阅读时长 ≈ 5 分钟

后缀数组 + 主席树

题意

给定长为 nn 的小写字符串 ss ， qq 次询问，每次询问子串 s[l,r]s[l,r] 中出现次数大于等于 22 的最长子串长度。
其中 1≤n≤5⋅104,1≤q≤1051 \leq n \leq 5 \cdot 10^4, 1 \leq q \leq 10^5 。

思路

容易发现答案具有二分性，对于每次询问，考虑二分满足条件的最长子串的长度 midmid ，单次询问即转换为判断区间 [l,r−mid+1][l,r-mid+1] 内的后缀两两之间的 lcplcp 的最大值是否大于等于 midmid 。
但是直接判断一遍是 O(n)O(n) 的，显然不合理，这里的判断需要用到另一题 P2178 [NOI2015] 品酒大会 的技巧：考虑求出串 ss 的后缀数组，将每个后缀 i(i≥2)i (i \geq 2) 按照 heightiheight_i 的值降序排序，两个后缀 x,yx, y 的 lcplcp 大于等于 midmid 当且仅当将所有 heighti≥midheight_i \geq mid 的后缀 ii 与后缀 i−1i-1 合并之后， x,yx, y 在同一连通块中。
那么二分出长度 midmid 后只需要判断将所有 heighti≥midheight_i \geq mid 的后缀 ii 与后缀 i−1i-1 合并之后，区间 [l,r−mid+1][l,r-mid+1] 内是否存在两点属于同一个连通块。若在每个节点标记上离它最近的下一个与它在同一连通块内的点的位置 nexnex ，判断过程就变成了查询区间 [l,r][l,r] 的最小值是否小于等于 rr ，那么这一过程的实现很容易想到用线段树维护。
由于将 heightiheight_i 排序后每次二分查询的相当于是 heightheight 数组的一段前缀的信息，可以考虑将排序后的 heightheight 数组可持久化。具体实现为：用第 ii 棵树维护当合并了所有 heighti≥iheight_i \geq i 的相邻后缀后，每个点的 nexnex 值与区间 minmin 。查询的时候直接查询第 midmid 棵树的信息即可。考虑用启发式合并的并查集维护每个后缀所属的连通块，那么每一次合并会修改若干个点的 nexnex 值，由于是启发式合并，总共的修改次数不会超过 n⋅lognn \cdot logn，因此建树的总复杂度是 O(n⋅log2n)O(n \cdot log^2n) ，具体用一个 setset 维护并查集，可以看代码实现。
每次查询时二分加查询的复杂度是 O(log2n)O(log^2n) ，因此总复杂度为 O(n⋅log2n)O(n \cdot log^2n) 。

代码

注意主席树上修改叶子时把该叶子的操作一次性做完。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;

constexpr int INF=0x3f3f3f3f;
constexpr int N=1e5+5;

vector<pii> vec,upd;
int n,q;
int fa[N];
set<int> st[N];
int len[N];
struct SA{
    int n,m;
    char s[N];
    int sa[N],rk[N],height[N],h[N];
    int minn[21][N],lg[N];
    void init(int _n,int _m){
        n=_n;
        m=_m;
    }
    void buildsa(){
        static int oldrk[N<<1],id[N],px[N],cnt[N];
        int i,p,w;
        for(i=1;i<=m+1;i++) cnt[i]=0;
        for(i=1;i<=n+1;++i) sa[i]=rk[i]=id[i]=px[i]=0;
        for(i=1;i<=n*2;i++) oldrk[i]=0;
        for(i=1;i<=n;++i) ++cnt[rk[i]=(s[i]-'a'+1)];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
        for(w=1;;w<<=1,m=p){
            for(p=0,i=n;i>n-w;--i) id[++p]=i;
            for(i=1;i<=n;++i)
            if(sa[i]>w) id[++p]=sa[i]-w;
            for(i=1;i<=m;i++) cnt[i]=0;
            for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
            for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
            for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
            for(i=1;i<=n;i++) oldrk[i]=rk[i];
            for(p=0,i=1;i<=n;++i)
            rk[sa[i]]=(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])?p:++p;
            if(p==n){
                for(i=1;i<=n;++i) sa[rk[i]]=i;
                break;
            }
        }
    }
    void buildheight(){
        for(int i=1;i<=n+1;++i) height[i]=h[i]=0;
        int k=0;
        for(int i=1;i<=n;i++){
            if(rk[i]==1) continue;
            if(k) --k;
            int j=sa[rk[i]-1];
            while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
            height[rk[i]]=k;
        }
        for(int i=1;i<=n;i++) h[i]=height[rk[i]];
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++) minn[0][i]=height[i];
        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++) minn[j][i]=min(minn[j-1][i],minn[j-1][i+(1<<(j-1))]);
    }
    int get_lcp(int l,int r){
        if(l==r) return n-l+1;
        l=rk[l],r=rk[r];
        if(l>r) swap(l,r);
        l++;
        int k=lg[r-l+1];
        return min(minn[k][l],minn[k][r-(1<<k)+1]);
    }
}sa;
struct tree{
    int tot;
    int rt[N];
    int lc[N<<6];
    int rc[N<<6];
    int minn[N<<6];
    void cpy(int x,int y){
        lc[x]=lc[y];
        rc[x]=rc[y];
        minn[x]=minn[y];
    }
    void build(int &x,int l,int r){
        x=++tot;
        minn[x]=INF;
        if(l==r) return;
        int mid=l+r>>1;
        build(lc[x],l,mid);
        build(rc[x],mid+1,r);
        return;
    }
    void update(int &x,int pre,int l,int r){
        if(upd.empty()||upd.back().first<l) return;
        x=++tot;
        cpy(x,pre);
        if(l==r){
            while(upd.size()&&upd.back().first==l){
                minn[x]=min(minn[x],upd.back().second);
                upd.pop_back();
            }
            return;
        }
        int mid=l+r>>1;
        update(rc[x],rc[pre],mid+1,r);
        update(lc[x],lc[pre],l,mid);
        minn[x]=min(minn[lc[x]],minn[rc[x]]);
        return;
    }
    int search(int x,int l,int r,int L,int R){
        if(L>R||!x) return INF;
        if(l>=L&&r<=R) return minn[x];
        int mi=INF;
        int mid=l+r>>1;
        if(mid>=L) mi=min(mi,search(lc[x],l,mid,L,R));
        if(mid+1<=R) mi=min(mi,search(rc[x],mid+1,r,L,R));
        return mi;
    }
}t;

int get(int a){
    if(fa[a]==a) return a;
    return fa[a]=get(fa[a]);
}

void merge(int a,int b){
    int r1=get(a),
        r2=get(b);
    if(r1==r2) return;
    if(st[r1].size()>st[r2].size()) swap(r1,r2);
    fa[r1]=r2;
    for(auto x:st[r1]){
        auto it=st[r2].upper_bound(x);
        if(it!=st[r2].end()) upd.push_back({x,(*it)});
        if(it!=st[r2].begin()){
            it=prev(it);
            upd.push_back({(*it),x});
        }
        st[r2].insert(x);
    }
    st[r1].clear();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>q;
    cin>>sa.s+1;
    sa.init(n,26);
    sa.buildsa();
    sa.buildheight();
    for(int i=1;i<=n;i++){
        fa[i]=i;
        st[i].insert(i);
    }
    for(int i=1;i<n;i++) vec.push_back({i,i+1});
    sort(vec.begin(),vec.end(),[&](const pii &a,const pii &b){
        return sa.get_lcp(sa.sa[a.first],sa.sa[a.second])>sa.get_lcp(sa.sa[b.first],sa.sa[b.second]);
    });
    t.build(t.rt[n+1],1,n);
    t.minn[0]=INF;
    int p=0;
    for(int i=0;i<vec.size();i++) len[i]=sa.get_lcp(sa.sa[vec[i].first],sa.sa[vec[i].second]);
    for(int i=n;i>=0;i--){
        upd.clear();
        while(p<vec.size()&&len[p]>=i){
            merge(sa.sa[vec[p].first],sa.sa[vec[p].second]);
            p++;
        }
        if(upd.size()){
            sort(upd.begin(),upd.end());
            t.update(t.rt[i],t.rt[i+1],1,n);
        }
        else{
            t.rt[i]=++t.tot;
            t.cpy(t.rt[i],t.rt[i+1]);
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        int L=0,R=n,ans=0;
        while(L<=R){
            int mid=L+R>>1;
            if(t.search(t.rt[mid],1,n,l,r-mid+1)<=r-mid+1) ans=mid,L=mid+1;
            else R=mid-1;
        }
        cout<<ans<<'\n';
    }

    return true&&false;
}