「十二省联考 2019」字符串问题
当场就去世了，我这菜人改了一下午
考虑一个A，B之间的连边实际表示了两个A之间的有向边，然后把A的连边处理好，就转成了拓扑排序找环+最长链
但是边数很多，考虑优化连边
A，B之间的连边显然没法优化的，考虑一个B可以表示所有它的后缀A
把串反向建出SAM，然后一个B的后缀就是par树的子树
可以拿倍增定位
好了这题就没了
注意到一个事情，定位的点可能重复，于是对SAM拆点，每个点挂一个vector表示一个A或者B的点在SAM的这个位置
然后考虑如何连边
一个B所可以代表的A的集合就是B所在位置的vector中长度不小于Ta的A以及par子树中的A
可以对每个点的vector排序，然后每个B连后面的A，直到下一个B出现或者末尾。
每个末尾的B像par树儿子的开头连边
然后A,B之间的连边照连
之后跑topo就可以了
复杂度(O(nlog n))，瓶颈在倍增和清空SAM
Code:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
#define ll long long
const int N=8e5+10;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int head[N],to[N<<1],Next[N<<1],in[N],cnt;
void add(int u,int v)
{
++in[v],to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int ch[N][26],len[N],par[N],tot=1,las=1;
void extend(int c)
{
int now=++tot,p=las;
len[now]=len[p]+1;
while(p&&!ch[p][c]) ch[p][c]=now,p=par[p];
if(!p) par[now]=1;
else
{
int x=ch[p][c];
if(len[x]==len[p]+1) par[now]=x;
else
{
int y=++tot;
par[y]=par[x];
len[y]=len[p]+1;
memcpy(ch[y],ch[x],sizeof ch[y]);
while(p&&ch[p][c]==x) ch[p][c]=y,p=par[p];
par[now]=par[x]=y;
}
}
las=now;
}
int f[20][N];
int Find(int x,int l)
{
for(int i=19;~i;i--)
if(len[f[i][x]]>=l)
x=f[i][x];
return x;
}
int na,nb,m;
int val[N],posa[N],posb[N];
ll dp[N];
int is[N],tot2,Las[N];
std::vector<int> yuy[N];
void Clear()
{
for(int i=1;i<=tot2;i++)
{
for(int j=0;f[j][i];j++)
f[j][i]=0;
in[i]=dp[i]=val[i]=0;
memset(ch[i],0,sizeof ch[i]);
par[i]=len[i]=0;
Las[i]=0;
head[i]=0;
is[i]=0;
yuy[i].clear();
}
for(int i=1;i<=na;i++) posa[i]=0;
for(int i=1;i<=nb;i++) posb[i]=0;
tot=las=1;
tot2=cnt=0;
}
char s[N];
int pos[N],tax[N],A[N],q[N];
bool cmp(int a,int b){return val[a]==val[b]?is[a]<is[b]:val[a]<val[b];}
void work()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=n;i;i--) extend(s[i]-'a'),pos[n+1-i]=las;
for(int i=0;i<=n;i++) tax[i]=0;
for(int i=1;i<=tot;i++) ++tax[len[i]];
for(int i=1;i<=n;i++) tax[i]+=tax[i-1];
for(int i=1;i<=tot;i++) A[tax[len[i]]--]=i;
for(int i=1;i<=tot;i++)
{
int now=A[i];
f[0][now]=par[now];
for(int j=1;f[j-1][now];j++)
f[j][now]=f[j-1][f[j-1][now]];
}
read(na);
tot2=tot;
for(int l,r,p,i=1;i<=na;i++)
{
read(l),read(r);
l=n+1-l,r=n+1-r;
p=Find(pos[l],l+1-r);
yuy[p].push_back(posa[i]=++tot2);
val[tot2]=l+1-r;
is[tot2]=1;
}
read(nb);
for(int l,r,p,i=1;i<=nb;i++)
{
read(l),read(r);
l=n+1-l,r=n+1-r;
p=Find(pos[l],l+1-r);
yuy[p].push_back(posb[i]=++tot2);
val[tot2]=l+1-r;
}
for(int i=1;i<=tot;i++)
{
std::sort(yuy[i].begin(),yuy[i].end(),cmp);
int las=i;
for(int j=0;j<yuy[i].size();j++)
{
int now=yuy[i][j];
add(las,now);
if(!is[now]) val[now]=0,las=now;
}
Las[i]=las;
}
for(int i=2;i<=tot;i++)
add(Las[par[i]],i);
read(m);
for(int u,v,i=1;i<=m;i++)
{
read(u),read(v);
u=posa[u],v=posb[v];
add(u,v);
}
int l=1,r=0;
ll mx=0;
for(int i=1;i<=tot2;i++)
if(!in[i])
q[++r]=i,mx=mx>val[i]?mx:val[i],dp[i]=val[i];
while(l<=r)
{
int now=q[l++];
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
--in[v];
dp[v]=std::max(dp[v],dp[now]+val[v]);
mx=mx>dp[v]?mx:dp[v];
if(!in[v]) q[++r]=v;
}
}
for(int i=1;i<=tot2;i++)
if(in[i])
{
puts("-1");
Clear();
return;
}
printf("%lld
",mx);
Clear();
}
int main()
{
int T;read(T);
while(T--) work();
return 0;
}
2019.4.9