当前位置: 首页 > news >正文

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;
}

完结撒花~

http://www.hskmm.com/?act=detail&tid=35364

相关文章:

  • 推荐系统与机器学习在会员服务中的应用
  • ManySpeech.MoonshineAsr 使用指南
  • 日志|JAVAWEB|maven
  • QT_基础
  • 2022 ICPC Hangzhou G and 2022 ICPC Jinan
  • C++在类定义内的函数包含static代表什么含义呢?
  • 2025/10/20~2025/?/? 做题笔记 - sb
  • 10-20 Extra-Problem 总结
  • ansible底层文件传输机制中默认模式遇到权限拒绝后启用管道模式可以得到解决
  • 10月20日记
  • Rust 编译加速的最佳实践
  • 20232304 2025-2026-1 《网络与系统攻防技术》实验三实验报告
  • 笔记本 光驱 的内部结构及用法: 应急强大的系统启动 (恢复) 光盘 (DVD+R/RW)
  • Android 源码解析系列1- Android init 进程启动流程
  • 分层图
  • 10.20总结
  • 学习相关
  • 题解:Luogu P10644 [NordicOI 2022] 能源网格 Power Grid
  • 题解:Luogu P10004 [集训队互测 2023] Permutation Counting 2
  • 题解:Luogu P2075 区间 LIS
  • 英语_阅读_2050 Space tourism_待读
  • goframe框架命令行工具gf在zsh下不能用
  • 题解:Luogu P4143 采集矿石
  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020