题解 P5284 【[十二省联考2019]字符串问题】
liuzhangfeiabc · · 题解
刚说完d1t1是道不错的温暖题，紧接着就来了一个令人发指的重工业。
题目大意：给定字符串s以及两类区间，再给定一些从第一类区间连向第二类区间的边，一个第二类区间能连向一个第一类区间当且仅当前者是后者的前缀。每个第一类区间的价值是区间长度，求这张图上的最长路（或判断无限长）。
emmmm...说道最长路，这显然是一个图论问题。如果这张图是给定的话，这就是一道小清新的noip题了：只需先跑个tarjan判断一个点是否能回到自己（能的话就是-1），然后在dag上dp即可。
然而...哪有这么简单的事啊！这明明是一道字符串题好伐！
我们需要考虑的就是，第二类区间向第一类区间的边该怎么连？
这里介绍一个我在考场上实现的后缀树做法：
每一个子串在后缀树上都对应一个节点，一个点的祖先对应的子串就是当前子串的前缀。
所以，我们只需要把每个子串都在后缀树上定位到节点，再对于每个第二类子串，向其子树内所有点连边即可。
什么？后缀树怎么建？sam总会吧（不会自行右转模板），反串的sam的parent树就是正串的后缀树啦。
子串定位的过程是通过倍增来实现的，先找到区间的左端点对应后缀的节点，再倍增地往上跳，直到这个点的len>=区间长度，它的fa的len<区间长度即可。
至于连边，当然可以dfs序上线段树优化建图（没错我考场上脑子一热写的就是这个），不过仔细想想发现这其实也没必要：你的后缀树本身就能直接帮你优化建图嘛。
于是你码啊码，终于在奋战2小时后，一份5k+的代码新鲜出炉了！
然而一测样例......蛤？怎么连小样例都过不去？！（小样例的最后一个点会被判成-1）
你冷静下来细细思考......等等，数据范围里的那个ai>=bj是干嘛的？
测一下ai>=bj的样例......居然过了......
那么ai<bj的时候会出现什么bug呢？
问题就出在后缀树上。一个后缀树上的节点可能对应多个长度不同的串，此时如果我们单纯地将每个第二类区间向其子树连边，就会错误地把当前节点上可能更短的第一类区间的点当成可以转移的点！
那怎么办？拆点！
一旦有这种情况的出现，我们就直接把这个点连向fa的边中间强行塞进去一堆点，此时再连边显然就是对的了。
总复杂度：除了子串定位部分是n log n，其它部分都是线性的（如果你没像我一样蠢到线段树优化建图的话）。
另外我感觉其实跑tarjan也是不需要的，只需要判一下是否有环即可，有环一定是-1。
于是，一份近9k的代码就这样诞生了......
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
inline li read(){
li x = 0,y = 0,c = gc;
while(c < '0' || c > '9') y = c,c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
return y == '-' ? -x : x;
}
inline void print(li x){
if(x < 0) pc('-'),x = -x;
if(x >= 10) print(x / 10);
pc(x % 10 + '0');
}
inline void file(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
}
char s[1000010];
int t,n,p1,p2,m;
struct node{
int l,r,x;
}a[1000010],b[1000010];
int tot = 1,lst = 1,son[400010][26],len[1000010],fa[1000010],wz[1000010];
inline int inss(int x){
int p = lst,np = ++tot;lst = np;len[np] = len[p] + 1;
for(;p && !son[p][x];p = fa[p]) son[p][x] = np;
if(!p) fa[np] = 1;
else{
int q = son[p][x];
if(len[q] == len[p] + 1) fa[np] = q;
else{
int nq = ++tot;
len[nq] = len[p] + 1;
memcpy(son[nq],son[q],sizeof(son[nq]));
fa[nq] = fa[q];
fa[q] = fa[np] = nq;
for(;son[p][x] == q;p = fa[p]) son[p][x] = nq;
}
}
return np;
}
int wei[1000010],nw,ed[1000010];
int val[3000010];
struct edge{
int to,nxt;
}e[20000010];
int cnt,fir[3000010],mx;
int fsts[1000010],nxts[1000010];
inline void dfs(int q){
wei[q] = ++nw;
for(int i = fsts[q];i;i = nxts[i]) dfs(i);
ed[q] = nw;
}
inline void dfs3(int q){
wei[q] = ++nw;
for(int i = fsts[q];i;i = nxts[i]) dfs3(i);
ed[q] = nw;
}
int st[20][1000010];
inline void buildst(){
register int i,j;
for(i = 1;i <= tot;++i) st[0][i] = fa[i];
for(i = 1;i <= 18;++i){
for(j = 1;j <= tot;++j) st[i][j] = st[i - 1][st[i - 1][j]];
}
}
inline int fd(int l,int r){
int nw = wz[l];
for(int i = 18;i >= 0;--i) if(len[st[i][nw]] >= r - l + 1) nw = st[i][nw];
return nw;
}
inline void ins(int u,int v){
//cerr<<u<<" "<<v<<"&"<<endl;
e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
mx = max(mx,max(u,v));
}
#define ls (q << 1)
#define rs (q << 1 | 1)
#define ln ls,l,mid
#define rn rs,mid + 1,r
#define md int mid = l + r >> 1
int www[1000010];
inline void build(int q,int l,int r){
if(l == r){
www[l] = q;
return;
}
md;
ins(q + p1 + p2,ls + p1 + p2);ins(q + p1 + p2,rs + p1 + p2);
build(ln);build(rn);
}
inline void xg(int q,int l,int r,int ax,int x){
if(l == r){
ins(q + p1 + p2,x);
return;
}
md;
if(mid >= ax) xg(ln,ax,x);
else xg(rn,ax,x);
}
inline void xg2(int q,int l,int r,int al,int ar,int x){
if(l >= al && r <= ar){
ins(x + p1,q + p1 + p2);
return;
}
md;
if(mid >= al) xg2(ln,al,ar,x);
if(mid < ar) xg2(rn,al,ar,x);
}
int dfn[3000010],low[3000010],bel[3000010],pp,sc;
vector<int> scc[3000010],qwq1[500010],qwq2[500010];
int pwp;
li an[3000010];
bool inst[3000010];
int stt[3000010],ft;
int qu[3000010],hh,tt,dus[3000010];
inline void tar(int q){
dfn[q] = low[q] = ++pp;
stt[++ft] = q;inst[q] = 1;
for(int i = fir[q];i;i = e[i].nxt){
if(!dfn[e[i].to]){
tar(e[i].to);low[q] = min(low[q],low[e[i].to]);
}
else if(inst[e[i].to]) low[q] = min(low[q],dfn[e[i].to]);
}
if(low[q] == dfn[q]){
int j;
++sc;
do{
j = stt[ft--];
bel[j] = sc;
inst[j] = 0;
scc[sc].push_back(j);
}while(j != q);
}
}
inline void wk(){
int i,j,l;
for(i = 1;i <= sc;++i) if(scc[i].size() > 1){
li vl = 0;
for(j = 0;j < scc[i].size();++j) vl += val[scc[i][j]];
if(vl > 0){
puts("-1");
return;
}
}
for(i = 1;i <= sc;++i){
for(j = 0;j < scc[i].size();++j){
for(l = fir[scc[i][j]];l;l = e[l].nxt) if(bel[e[l].to] != i) ++dus[bel[e[l].to]];
}
}
hh = tt = 0;
for(i = 1;i <= sc;++i) if(!dus[i]) qu[++tt] = i;
while(hh < tt){
i = qu[++hh];
for(j = 0;j < scc[i].size();++j){
an[i] += val[scc[i][j]];
for(l = fir[scc[i][j]];l;l = e[l].nxt) if(bel[e[l].to] != i){
an[bel[e[l].to]] = max(an[bel[e[l].to]],an[i]);
--dus[bel[e[l].to]];
if(!dus[bel[e[l].to]]) qu[++tt] = bel[e[l].to];
}
}
}
li ans = 0;
for(i = 1;i <= sc;++i) ans = max(ans,an[i]);
print(ans);pc('\n');
}
inline bool cmp1(int q,int w){
return a[q].r - a[q].l > a[w].r - a[w].l;
}
inline bool cmp2(int q,int w){
return b[q].r - b[q].l > b[w].r - b[w].l;
}
void dfs2(int q){
//cerr<<q<<" "<<len[q]<<endl;
if(q != 1 && (qwq1[q].size() != 0 || qwq2[q].size() != 0)){
int nwq = q,i = 0,j = 0,lst = len[q],nxt,nxtq;
while(i < qwq1[q].size() && j < qwq2[q].size()){
//cerr<<i<<" "<<j<<"()"<<" "<<qwq1[q].size()<<" "<<qwq2[q].size()<<endl;
if(a[qwq1[q][i]].r - a[qwq1[q][i]].l > b[qwq2[q][j]].r - b[qwq2[q][j]].l){
nxt = a[qwq1[q][i]].r - a[qwq1[q][i]].l + 1;
if(nxt == lst) a[qwq1[q][i]].x = nwq;
else{
nxtq = ++tot;
fa[nxtq] = fa[nwq];
fa[nwq] = nxtq;
len[nxtq] = nxt;
a[qwq1[q][i]].x = nxtq;
nwq = nxtq;
}
lst = nxt;++i;
}
else{
nxt = b[qwq2[q][j]].r - b[qwq2[q][j]].l + 1;
if(nxt == lst) b[qwq2[q][j]].x = nwq;
else{
nxtq = ++tot;
fa[nxtq] = fa[nwq];
fa[nwq] = nxtq;
len[nxtq] = nxt;
b[qwq2[q][j]].x = nxtq;
nwq = nxtq;
}
lst = nxt;++j;
}
}
//cerr<<"*"<<endl;
while(i < qwq1[q].size()){
nxt = a[qwq1[q][i]].r - a[qwq1[q][i]].l + 1;
if(nxt == lst) a[qwq1[q][i]].x = nwq;
else{
nxtq = ++tot;
fa[nxtq] = fa[nwq];
fa[nwq] = nxtq;
len[nxtq] = nxt;
a[qwq1[q][i]].x = nxtq;
nwq = nxtq;
}
lst = nxt;++i;
}
while(j < qwq2[q].size()){
nxt = b[qwq2[q][j]].r - b[qwq2[q][j]].l + 1;
if(nxt == lst) b[qwq2[q][j]].x = nwq;
else{
nxtq = ++tot;
fa[nxtq] = fa[nwq];
fa[nwq] = nxtq;
len[nxtq] = nxt;
b[qwq2[q][j]].x = nxtq;
nwq = nxtq;
}
lst = nxt;++j;
}
}
for(int i = fsts[q];i;i = nxts[i]) dfs2(i);
}
int main(){
//file();
int i,j,u,v,mx1,mx2;
t = read();
while(t--){
scanf("%s",s + 1);n = strlen(s + 1);
for(i = n;i;--i) wz[i] = inss(s[i] - 'a');
//cerr<<tot<<"*"<<endl;
//for(i = 1;i <= tot;++i) cerr<<fa[i]<<" ";cerr<<endl;
//for(i = 1;i <= tot;++i) cerr<<len[i]<<" ";cerr<<endl;
//for(i = 1;i <= n;++i) cerr<<wz[i]<<" ";cerr<<endl;
for(i = 2;i <= tot;++i) nxts[i] = fsts[fa[i]],fsts[fa[i]] = i;
dfs(1);buildst();
//for(i = 1;i <= tot;++i) cerr<<wei[i]<<" ";cerr<<endl;
//for(i = 1;i <= tot;++i) cerr<<ed[i]<<" ";cerr<<endl;
mx1 = n;
mx2 = 0;
p1 = read();
for(i = 1;i <= p1;++i){
a[i].l = read();a[i].r = read();mx1 = min(mx1,a[i].r - a[i].l + 1);
a[i].x = fd(a[i].l,a[i].r);val[i] = a[i].r - a[i].l + 1;
}
p2 = read();
for(i = 1;i <= p2;++i){
b[i].l = read();b[i].r = read();mx2 = max(mx2,b[i].r - b[i].l + 1);
b[i].x = fd(b[i].l,b[i].r);
}
pwp = tot;
if(mx1 < mx2){
//cerr<<"***"<<endl;
for(i = 1;i <= p1;++i) qwq1[a[i].x].push_back(i);
for(i = 1;i <= p2;++i) qwq2[b[i].x].push_back(i);
for(i = 1;i <= tot;++i) sort(qwq1[i].begin(),qwq1[i].end(),cmp1),sort(qwq2[i].begin(),qwq2[i].end(),cmp2);
//cerr<<"&&&"<<tot<<endl;
dfs2(1);
//cerr<<"()"<<endl;
for(i = 1;i <= tot;++i) nxts[i] = fsts[i] = 0;
nw = 0;
for(i = 2;i <= tot;++i) nxts[i] = fsts[fa[i]],fsts[fa[i]] = i;
dfs3(1);
//cerr<<tot<<endl;
}
build(1,1,tot);
for(i = 1;i <= p1;++i){
ins(www[wei[a[i].x]] + p1 + p2,i);
//cerr<<a[i].l<<" "<<a[i].r<<" "<<a[i].x<<" "<<wei[a[i].x]<<"()"<<endl;
//xg(1,1,tot,wei[a[i].x],i);
}
for(i = 1;i <= p2;++i){
//cerr<<b[i].l<<" "<<b[i].r<<" "<<b[i].x<<" "<<wei[b[i].x]<<" "<<ed[b[i].x]<<"&&"<<endl;
xg2(1,1,tot,wei[b[i].x],ed[b[i].x],i);
}
m = read();
for(i = 1;i <= m;++i) u = read(),v = read(),ins(u,v + p1);
//return 0;
for(i = 1;i <= mx;++i) if(!dfn[i]) tar(i);
wk();
//cerr<<mx<<" "<<pwp<<" "<<tot<<endl;return 0;
for(i = 1;i <= n;++i) s[i] = wz[i] = 0;
for(i = 1;i <= pwp;++i) memset(son[i],0,sizeof(son[i]));
for(i = 1;i <= tot;++i) fa[i] = len[i] = wei[i] = ed[i] = fsts[i] = nxts[i] = www[i] = 0;
for(i = 1;i <= mx;++i) fir[i] = val[i] = dfn[i] = low[i] = bel[i] = an[i] = 0;
for(i = 1;i <= sc;++i) scc[i].clear();
for(i = 1;i <= pwp;++i) qwq1[i].clear(),qwq2[i].clear();
tot = lst = 1;
cnt = mx = nw = pp = sc = hh = tt = ft = pwp = 0;
}
return 0;
}