CF666E Forensic Examination 题解
一、题目描述：
给你一个长度为 $n$ 模板串 $S$ 以及 $m$ 个匹配串 $T$。
$q$ 次询问，给定 $l,r,L,R$，询问 $S_l\sim S_r$ 在 $T_L\sim T_R$ 中出现次数最多的字符串编号以及最多的出现次数。
注意，若有多个出现次数最多的字符串，取编号最小的那一个。
数据范围：$1\le n,q\le 5\times 10^5,1\le m\le 5\times 10^4,1\le \sum_{i=1}^m len_{T_i}\le 5e4$
二、解题思路：
只会 $SA$。
然后就是 $height$ 数组上求出现次数最多的 $T$，这是明显的回滚莫队。
但是这题求得是区间最大值，所以再加一个分块记录区间答案。
怎么样，说起来简单吧？巨大难写！巨大难调！时间复杂度 $O(nlog_2^n+n\sqrt n)$，常数极大。
三、完整代码：
1 #include<bits/stdc++.h> 2 #define N 1000010 3 #define rep(i,l,r) for(int i=l;i<=r;i++) 4 #define per(i,r,l) for(int i=r;i>=l;i--) 5 using namespace std; 6 int n,m,num,p=122; 7 int base[20],st[N][20],val[N]; 8 int s[N],h[N],tp[N],sa[N],rak[N]; 9 int c[N],mx[N],tag[N],ans[N],cnt[N]; 10 int k[N],t[N],T[N],head,tail,sn; 11 struct ST{ 12 int l,r,id; 13 bool operator != (const ST &t) const{ 14 return (l!=t.l||r!=t.r); 15 } 16 }a[N],b[N]; 17 struct Query{ 18 int l,r,L,R,id; 19 bool operator < (const Query &t) const{ 20 if(k[l]!=k[t.l]) return l<t.l; 21 else return r<t.r; 22 } 23 }q[N]; 24 void qsort(){ 25 rep(i,0,m) tp[i]=0; 26 rep(i,1,n) tp[a[i].r]++; 27 rep(i,1,m) tp[i]+=tp[i-1]; 28 per(i,n,1) b[tp[a[i].r]--]=a[i]; 29 rep(i,0,m) tp[i]=0; 30 rep(i,1,n) tp[b[i].l]++; 31 rep(i,1,m) tp[i]+=tp[i-1]; 32 per(i,n,1) a[tp[b[i].l]--]=b[i]; 33 } 34 void suffixsort(){ 35 rep(i,1,n) rak[i]=s[i]; 36 for(int w=1;w<=n;w<<=1){ 37 rep(i,1,n) a[i]={rak[i],rak[i+w],i}; 38 m=p; p=0; qsort(); 39 rep(i,1,n) rak[a[i].id]=(p+=a[i]!=a[i-1]); 40 if(p==n) break; 41 } 42 rep(i,1,n) sa[rak[i]]=i; 43 } 44 void get_height(){ 45 int k=0; 46 rep(i,1,n){ 47 if(k) k--; 48 int j=sa[rak[i]-1];if(!j) continue; 49 while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n) k++; 50 h[rak[i]]=k; 51 } 52 } 53 void rebuild_ST(){ 54 base[0]=1; 55 rep(i,1,n) st[i][0]=h[i]; 56 rep(i,1,n) val[i]=log(i)/log(2); 57 rep(i,1,19) base[i]=base[i-1]<<1; 58 rep(i,1,19) rep(j,1,n){ 59 st[j][i]=st[j][i-1]; int k=j+base[i-1]; 60 if(k<=n) st[j][i]=min(st[j][i],st[k][i-1]); 61 } 62 } 63 int calc(int l,int r){ 64 int k=val[r-l+1]; 65 return min(st[l][k],st[r-base[k]+1][k]); 66 } 67 void Insert(int id){ 68 string x; cin>>x; int len=x.length(); 69 s[n+1]=++p; n+=len+1; 70 rep(i,n-len+1,n) s[i]=x[i-n+len-1],c[i]=id; 71 } 72 int Find_L(int pos,int val){ 73 int l=1,r=pos,res=pos; 74 while(l<=r){ 75 int mid=(l+r)>>1; 76 if(calc(mid,pos)>=val) res=r=mid-1; 77 else l=mid+1; 78 } return res; 79 } 80 int Find_R(int pos,int val){ 81 int l=pos+1,r=n,res=pos; 82 while(l<=r){ 83 int mid=(l+r)>>1; 84 if(calc(pos+1,mid)>=val) res=mid,l=mid+1; 85 else r=mid-1; 86 } return res; 87 } 88 void upt(int id){ 89 tail=id*sn; rep(i,1,max(n,m)) t[i]=mx[i]=0; 90 } 91 void baoli(int id){ 92 int res=q[id].L; 93 rep(i,q[id].l,q[id].r){ 94 int v=c[sa[i]];T[v]++; 95 if(q[id].L<=v&&v<=q[id].R){ 96 if(T[v]>T[res]) res=v; 97 if(T[v]==T[res]&&v<res) res=v; 98 } 99 } 100 ans[q[id].id]=res;cnt[q[id].id]=T[res]; 101 rep(i,q[id].l,q[id].r) T[c[sa[i]]]=0; 102 } 103 void mdf(int id,int v,int pos){ 104 if(v>cnt[id]) cnt[id]=v,ans[id]=pos; 105 if(v==cnt[id]&&pos<ans[id]) ans[id]=pos; 106 } 107 void add(int pos){ 108 int v=c[sa[pos]]; t[v]++; 109 if(t[v]>mx[k[v]]) mx[k[v]]=t[v],tag[k[v]]=v; 110 if(t[v]==mx[k[v]]&&v<tag[k[v]]) tag[k[v]]=v; 111 } 112 void add1(int id,int pos){ 113 int u=c[sa[pos]]; T[u]++; 114 if(q[id].L<=u&&u<=q[id].R) mdf(q[id].id,t[u]+T[u],u); 115 } 116 int main(){ 117 ios::sync_with_stdio(false); 118 cin.tie(0);cout.tie(0); 119 string x; cin>>x; n=x.length(); 120 rep(i,1,n) s[i]=x[i-1],c[i]=1e5; 121 cin>>num; rep(i,1,num) Insert(i); 122 suffixsort(); get_height(); rebuild_ST(); 123 cin>>num; rep(i,1,num){ 124 int _l,_r,_L,_R; 125 cin>>_L>>_R>>_l>>_r; 126 int nl=Find_L(rak[_l],_r-_l+1); 127 int nr=Find_R(rak[_l],_r-_l+1); 128 q[i]={nl,nr,_L,_R,i}; 129 } 130 sn=sqrt(n); rep(i,1,n) k[i]=(i+sn-1)/sn; 131 sort(q+1,q+1+num); 132 rep(i,1,num){ 133 if(k[q[i].l]!=k[q[i-1].l]) upt(k[q[i].l]); 134 if(k[q[i].l]==k[q[i].r]) {baoli(i);continue;} 135 while(tail<q[i].r) tail++,add(tail); 136 rep(j,q[i].l,k[q[i].l]*sn) add1(i,j); 137 rep(j,q[i].l,k[q[i].l]*sn) T[c[sa[j]]]=0; 138 if(k[q[i].L]==k[q[i].R]){ 139 rep(j,q[i].L,q[i].R) mdf(q[i].id,t[j],j); 140 if(!cnt[q[i].id]) ans[q[i].id]=q[i].L; 141 continue; 142 } 143 int now=k[q[i].L]+1;while(q[i].R>=now*sn) 144 mdf(q[i].id,mx[now],tag[now]),now++; 145 rep(j,(now-1)*sn+1,q[i].R) mdf(q[i].id,t[j],j); 146 rep(j,q[i].L,k[q[i].L]*sn) mdf(q[i].id,t[j],j); 147 if(!cnt[q[i].id]) ans[q[i].id]=q[i].L; 148 } 149 rep(i,1,num) cout<<ans[i]<<" "<<cnt[i]<<'\n'; 150 return 0; 151 }
四、写题心得：
很难写，收获很大：
$1、离谱，顺带把回滚莫队学了。=> Exp++!$
$2、细节巨多，找问题的能力、码力大幅提升=> Exp++!$