P11150 [THUWC 2018] 字胡串

P11150 [THUWC 2018] 字胡串

P11150 [THUWC 2018] 字胡串

思路

若 \(S + T\) 的字典序小于 \(T + S\) 的字典序则称 \(S < T\)，若 \(S + T\) 的字典序小于等于 \(T + S\) 的字典序则称 \(S \le T\)。

容易注意到如果答案是 \(j\) 则 \(B \le A_{j+1,n}\)。
而 \(\forall 1 \le i \le j\)，\(A_{1,i} < B\)。考虑把 \(A\) 划分成 \(T\) 个段 \(S_1, S_2 · · · S_T\) 使得 \(\forall 1 \le i < T, S_i < S_{i+1}\)。

显然有多种划分方式，但是我们取 \(|Si|\) 组成的序列字典序最小的。易证对于查询串 \(B\) 一定只会在 \(S_k\) 与 \(S_{k+1}\) 之间插入而不会在 \(S_k\) 内部插入。二分出在哪一段插入，用哈希加二分判 \(B < S_k\) 是否为真即可。

时间复杂度 \(O (q \log n \log (n + m))\)。

Code

#include<iostream>
#include<set>
#include<string>
#include<cstring>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
const int base=71;
string str;
bool vis[N];
int n,m,Q,a[N],b[N],tot=0,border[N],father[N],fa_L[N],fa_R[N];
unsigned long long Hash_A[N],Hash_B[N],power[N];
unsigned long long Calc_A(int L,int R)
{return Hash_A[R]-Hash_A[L-1]*power[R-L+1];
}
int Find(int k)
{if(father[k]!=k) return father[k]=Find(father[k]);return k;
}
struct Node
{int L_bound,R_bound;friend bool operator==(Node x,Node y){return x.L_bound==y.L_bound&&x.R_bound==y.R_bound;}friend bool operator<(Node x,Node y){int len=0,pos=0,l=1,r=0,L=0,R=0;len=min(x.R_bound-x.L_bound+1,y.R_bound-y.L_bound+1);if(Calc_A(x.L_bound,x.L_bound+len-1)!=Calc_A(y.L_bound,y.L_bound+len-1)){l=1,r=len,L=x.L_bound,R=y.L_bound;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L,L+Mid-1)!=Calc_A(R,R+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+pos-1]<a[R+pos-1];}if(x.R_bound-x.L_bound==y.R_bound-y.L_bound)return x.L_bound>y.L_bound;if(x.R_bound-x.L_bound>y.R_bound-y.L_bound){if(Calc_A(x.L_bound+len,x.R_bound)==Calc_A(x.L_bound,x.R_bound-len)){if(Calc_A(y.L_bound,y.R_bound)==Calc_A(x.R_bound-y.R_bound+y.L_bound,x.R_bound))return x.L_bound>y.L_bound;l=1,r=y.R_bound-y.L_bound+1,L=y.L_bound,R=x.R_bound-y.R_bound+y.L_bound;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L,L+Mid-1)!=Calc_A(R,R+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+pos-1]<a[R+pos-1];}else{l=1,r=x.R_bound-x.L_bound-len+1,L=x.L_bound+len,R=x.L_bound;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L,L+Mid-1)!=Calc_A(R,R+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+pos-1]<a[R+pos-1];}}else{if(Calc_A(y.L_bound+len,y.R_bound)==Calc_A(y.L_bound,y.R_bound-len)){if(Calc_A(x.L_bound,x.R_bound)==Calc_A(y.R_bound-x.R_bound+x.L_bound,y.R_bound))return y.L_bound<x.L_bound;l=1,r=x.R_bound-x.L_bound+1,L=x.L_bound,R=y.R_bound-x.R_bound+x.L_bound;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L,L+Mid-1)!=Calc_A(R,R+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+pos-1]>a[R+pos-1];}else{l=1,r=y.R_bound-y.L_bound-len+1,L=y.L_bound+len,R=y.L_bound;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L,L+Mid-1)!=Calc_A(R,R+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+pos-1]>a[R+pos-1];}}}
}x;
unsigned long long Calc_B(int L,int R)
{return Hash_B[R]-Hash_B[L-1]*power[R-L+1];
}
bool Check(int L,int R)
{int len=0,pos=0,l=1,r=0;len=min(m,R-L+1);if(Calc_A(L,L+len-1)!=Calc_B(1,len)){l=1,r=len;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L,L+Mid-1)!=Calc_B(1,Mid))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+pos-1]<b[pos];}if(R-L+1==m)return 0;if(R-L+1>m){len=R-L-m+1;if(Calc_A(L+m,R)==Calc_A(L,L+len-1)){if(Calc_B(1,m)==Calc_A(R-m+1,R))return 0;l=1,r=m;while(l<=r){int Mid=(l+r)>>1;if(Calc_B(1,Mid)!=Calc_A(R-m+1,R-m+Mid))pos=Mid,r=Mid-1;elsel=Mid+1;}return b[pos]<a[R-m+pos];}else{l=1,r=R-L+1-m;while(l<=r){int Mid=(l+r)>>1;if(Calc_A(L+m,L+m+Mid-1)!=Calc_A(L,L+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return a[L+m+pos-1]<a[L+pos-1];}}else{len=m-(R-L+1);if(Calc_B(1,len)==Calc_B(m-len+1,m)){if(Calc_B(len+1,m)==Calc_A(L,R))return 0;l=1,r=R-L+1;while(l<=r){int Mid=(l+r)>>1;if(Calc_B(len+1,len+Mid)!=Calc_A(L,L+Mid-1))pos=Mid,r=Mid-1;elsel=Mid+1;}return b[len+pos]<a[L+pos-1];}else{l=1,r=len;while(l<=r){int Mid=(l+r)>>1;if(Calc_B(1,Mid)!=Calc_B(m-len+1,m-len+Mid))pos=Mid,r=Mid-1;elsel=Mid+1;}return b[pos]<b[m-len+pos];}}
}
set<Node>S;
int main()
{// freopen("string.in","r",stdin);// freopen("string.out","w",stdout);IOS;power[0]=1;for(int i=1;i<N;i++)power[i]=power[i-1]*base;cin>>n>>Q>>str;str=" "+str;for(int i=1;i<=n;i++)a[i]=str[i]-'0',Hash_A[i]=Hash_A[i-1]*base+a[i];for(int i=1;i<=n;i++){x.L_bound=x.R_bound=i;S.insert(x);father[i]=fa_L[i]=fa_R[i]=i;}vis[0]=true;for(int i=1;i<=n;i++){Node tmp=*S.begin();S.erase(S.begin());if(vis[Find(tmp.L_bound-1)]){border[++tot]=tmp.R_bound;vis[Find(tmp.L_bound)]=true;continue;}x.R_bound=tmp.L_bound-1,x.L_bound=fa_L[Find(x.R_bound)];S.erase(x);father[Find(tmp.L_bound)]=Find(x.L_bound);fa_L[Find(tmp.L_bound)]=x.L_bound;fa_R[Find(tmp.R_bound)]=tmp.R_bound;x.R_bound=tmp.R_bound;S.insert(x);}while(Q--){cin>>str;str=" "+str;m=str.size()-1;for(int i=1;i<=m;i++)b[i]=str[i]-'0',Hash_B[i]=Hash_B[i-1]*base+b[i];int L=1,R=tot,pos=0;while(L<=R){int Mid=(L+R)>>1;if(Check(border[Mid-1]+1,border[Mid]))pos=Mid,L=Mid+1;elseR=Mid-1;}cout<<border[pos]<<'\n';}return 0;
}

完结撒花~