题解 P5284 【[十二省联考2019]字符串问题】
cosmicAC
2019-04-08 13:20:54
下面是我的后缀数组解法。
首先考虑前80分的做法，和其他所有题解一样，是要把“T的分割中，y可作为x的后一个串”这个关系用有向图表示出来，然后只要判断是不是DAG。如果是那么跑最长路，否则-1。这里判DAG其实可以和求拓扑序一起做，如果跑完拓扑序之后还有未到达的点的话就不是DAG。
然后考虑建图方法。枚举一个A串，枚举被A串支配的所有B串，由于前80分中的$\forall{i,j},|A_i|\ge|B_j|$限制，"存在一个前缀是B的串组成的集合"是后缀数组上的一个区间，起始点在区间中的所有A串都是合法的。只要对这个区间中所有的A串连边即可。找区间的时候可以在height数组上建ST表倍增（或二分），复杂度都是一个log的。
然后是建边，暴力建边的话边数是$n^2$级别的肯定不行。然而可以利用ST表建边，比如区间是$[l,r]$，$k=\lfloor\log_2{(r-l+1)}\rfloor$，就向表示$[l,l+2^k),[r+1-2^k,r]$的两个点连边即可。这样就可以得到80分。
然后是满分算法。可以看出，唯一的区别是开始位置相同的一些A串中，只有较长的一部分串可以连边。这就是二维偏序了，我在考场上以为要树套树所以不可做。后来发现用不着，可以交换一下两维，使得第一维是A串长度，第二维是A串开始位置的rank。这样第一维就变成了前缀，所以可以用主席树优化建图，点数和边数的规模都是一个log的。
可惜由于常数远大于SAM，洛谷过不去。loj上可以通过的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=200010;
char s[maxn];ll dis[maxn*25];
int n,sa[maxn],nr[maxn*2],rnk[maxn*2],st[maxn][20],hd[maxn*25],p[maxn],ind[maxn*25];
int T,tot,m,na,nb,w[maxn*25],l[maxn],r[maxn],que[maxn*25],rt[maxn],ps[maxn];
struct stt{int l,r,id;}a[maxn];vector<stt> u;
bool operator<(stt a,stt b){return a.r-a.l>b.r-b.l;}
vector<int> v[maxn];
struct edge{int v,nxt;}e[maxn*100];
void adde(int a,int b){e[++m]={b,hd[a]};hd[a]=m;ind[b]++;}
int qry1(int p,int vl){
for(int k=19;~k;k--)if(p>=1<<k&&st[p-(1<<k)+1][k]>=vl)p-=1<<k;
return p;
}
int qry2(int p,int vl){
for(int k=19;~k;k--)if(p+(1<<k)<=n+1&&st[p][k]>=vl)p+=1<<k;
return p-1;
}
struct segTree{
int L[maxn*25],R[maxn*25];
void ins(int id,int p,int tl=1,int tr=n){
if(tl==tr){adde(++tot,p);u.push_back({tot,id});return;}
int mid=tl+tr>>1;
if(rnk[a[id].l]<=mid)ins(id,L[p],tl,mid),R[++tot]=R[p],L[tot]=tot-1;
else ins(id,R[p],mid+1,tr),L[++tot]=L[p],R[tot]=tot-1;
adde(tot,p),adde(tot,tot-1);
}
void add(int l,int r,int x,int p,int tl=1,int tr=n){
if(l<=tl&&tr<=r){adde(x,p);return;}
int mid=tl+tr>>1;
if(l<=mid)add(l,r,x,L[p],tl,mid);
if(r>mid)add(l,r,x,R[p],mid+1,tr);
}
}tr;
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+1);n=strlen(s+1);
memset(nr,0,sizeof nr),memset(rnk,0,sizeof rnk);
for(int i=1;i<=n;i++)rnk[i]=s[i],sa[i]=i;
for(int i=1;i<=n;i<<=1){
sort(sa+1,sa+1+n,[&](int a,int b){
return rnk[a]<rnk[b]||rnk[a]==rnk[b]&&rnk[a+i]<rnk[b+i];
});
for(int j=1,t=0;j<=n;nr[sa[j++]]=t)
t+=rnk[sa[j]]!=rnk[sa[j-1]]||rnk[sa[j]+i]!=rnk[sa[j-1]+i];
memcpy(rnk,nr,sizeof nr);
}
for(int i=1,k=0;i<=n;i++){
if(k)k--;
for(;s[i+k]==s[sa[rnk[i]-1]+k];k++);
*st[rnk[i]]=k;
}
memset(hd,0,sizeof hd);
memset(w,0,sizeof w);
memset(ind,0,sizeof ind);
tot=m=0;u.clear();
memset(&tr,0,sizeof tr);
for(int i=1;(1<<i)<=n;i++)
for(int j=0;j+(1<<i)<=n+1;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
scanf("%d",&na);
for(int i=1;i<=n;i++)v[i].clear();
for(int i=1;i<=na;i++)
scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
sort(a+1,a+1+na);
for(int i=1;i<=na;i++)
ps[a[i].id]=i,tr.ins(i,rt[i-1]),rt[i]=tot;
for(int i=1;i<=na;i++)w[p[i]=++tot]=a[i].r-a[i].l+1;
for(stt&s:u)adde(s.l,p[s.r]);
scanf("%d",&nb);
for(int i=1;i<=nb;i++)scanf("%d%d",l+i,r+i);
int x;scanf("%d",&x);
for(int i=1;i<=x;i++){
int x,y;scanf("%d%d",&x,&y);
v[ps[x]].push_back(y);
}
for(int i=1;i<=na;i++)for(int j:v[i]){
int x=qry1(rnk[l[j]],r[j]-l[j]+1),y=qry2(rnk[l[j]]+1,r[j]-l[j]+1);
tr.add(x,y,p[i],rt[upper_bound(a+1,a+1+na,stt{l[j],r[j]})-a-1]);
}
memset(dis,0,sizeof dis);
int l=1,r=0;
for(int i=1;i<=tot;i++)if(!ind[i])que[++r]=i,dis[i]=w[i];
while(l<=r){
int p=que[l++];
for(int x=hd[p];x;x=e[x].nxt){
dis[e[x].v]=max(dis[e[x].v],dis[p]+w[e[x].v]);
if(!--ind[e[x].v])que[++r]=e[x].v;
}
}
if(r!=tot+1)puts("-1");else printf("%lld\n",*max_element(dis+1,dis+1+tot));
}
return 0;
}
```