目录
@description@
现有一个字符串 S。
Tiffany 将从中划分出 na 个子串作为 A 类串，第 i 个 Ai = S[la[i]...ra[i]]。
Yazid 将从中划分出 nb 个子串作为 B 类串，第 i 个 Bi = S[lb[i]...rb[i]]。
给定 m 组支配关系 (x, y)，表示第 x 的 A 类串支配第 y 的 B 类串。
请使用任意多个 A 类串拼接起来得到最长的目标串 T，满足对于两个相邻的 A 类串，前一个 A 类串支配的某个 B 类串是后一个 A 类串的前缀。
如果无限长，输出 -1。
输入格式
从标准输入读入数据。
单个测试点中包含多组数据，输入的第一行包含一个非负整数 T 表示数据组数。接下来依次描述每组数据，对于每组数据：
第 1 行一个只包含小写字母的字符串 S。
第 2 行一个非负整数 na，表示 A 类串的数目。接下来 na 行，每行 2 个用空格隔开的整数。
这部分中第 i 行的两个数分别为 la[i], ra[i]，描述第 i 个 A 类串。
保证 1 <= la[i] <= ra[i] <= |S|。
接下来一行一个非负整数 nb，表示 B 类串的数目。接下来 nb 行，每行 2 个用空格隔开的整数。
这部分中第 i 行的两个数分别为 lb[i], rb[i]，描述第 i 个 B 类串。
保证 1 <= lb[i] <= rb[i] <= |S|。
接下来一行一个非负整数 m，表示支配关系的组数。接下来 m 行，每行 2 个用空格隔开的整数。
这部分中每行的两个整数 x, y，描述一对 (x, y) 的支配关系，具体意义见「题目描述」。
保证 1 <= x <= na，1 <= y <= nb。保证所有支配关系两两不同，即不存在两组支配关系的 x, y 均相同。
输出格式
输出到标准输出。
依次输出每组数据的答案，对于每组数据：
一行一个整数表示最大串长。特别地，如果满足限制的串可以是无限长的，则请输出 -1。
样例输入 1
3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1
样例输出 1
7
-1
13
样例说明 1
对于第 1 组数据，A 类串有 aaba 与 aba，B 类串有 aa，且 A2 支配 B1。我们可以找到串 abaaaba，它可以拆分成 A2 + A1，且 A1 包含由 A2 所支配的 B1 作为前缀。可以证明不存在长度更大的满足限制的串。
对于第 2 组数据，与第 1 组数据唯一不同的是，唯一的 B 类串为 a。容易证明存在无限长的满足限制的串。
对于第 3 组数据，容易证明 abbaabbaaaabb 是最长的满足限制的串。
数据范围与提示
对于所有测试点中的每一组数据，保证：1 <= |S| <= 2*10^5，na, nb <= 2*10^5，m <= 2*10^5。
且 |S|, na, nb, m 的总和的总和分别不会超过该测试点中对应的单组数据的限制的 10 倍。
@solution@
每一个 Ai 后面能够接的 A 类串的集合是固定的，于是我们可以将 Ai 向它后面能够接的 A 类串连边。
跑一个简单的拓扑排序，如果有环则无解，否则可以边排序边 DAG 上 dp 求最大值。
现在考虑优化一下建边。
我们可以每一个 A 类串向它支配的 B 类串连边，每一个 B 类串向以这个 B 类串为前缀的 A 类串连边。
前半部分的连边是 O(m) 的，我们继续考虑优化后面部分。
如果 Bj = S[lb[j]...rb[j]] 是 Ai = S[la[i]...ra[i]] 的前缀，则这个条件其实与 |Ai| >= |Bj| 且 lcp(lb[j], la[i]) >= |Bj| 等价。
而通过后缀数组可以得知，与后缀 lb[j] 的 lcp >= 某个值的后缀实际上形成一个区间。
于是可以考虑用可持久化线段树辅助我们连边。
具体来说，我们将 A、B 按照其长度一起排序，从大到小依次考虑串，先考虑 A 类串再考虑 B 类串。
对于 A 类串，直接丢入线段树中其 rank 对应的位置即可。
对于 B 类串，我们首先二分找到 lcp >= |Bj| 的对应区间，然后向这个区间连边即可。
时间复杂度和空间复杂度都是 O(nlogn)。
@accepted code@
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 200000;
struct edge{
int to; edge *nxt;
}edges[80*MAXN + 5], *adj[45*MAXN + 5], *ecnt;
int ind[45*MAXN + 5];
void addedge(int u, int v) {
edge *p = (++ecnt);
p->to = v, p->nxt = adj[u], adj[u] = p;
ind[v]++;
// printf("! %d %d\n", u, v);
}
struct node{
int l, r, id;
node(int _l=0, int _r=0):l(_l), r(_r) {}
int len() {return r - l + 1;}
friend bool operator < (node x, node y) {return x.len() < y.len();}
}a[MAXN + 5], b[MAXN + 5];
char S[MAXN + 5];
int sa[MAXN + 5], rnk[MAXN + 5], c[MAXN + 5];
int nsa[MAXN + 5], nrnk[MAXN + 5];
int na, nb, m, lenS;
void get_sa(int n, int m) {
for(int i=0;i<m;i++) c[i] = 0;
for(int i=0;i<n;i++) c[S[i]]++;
for(int i=1;i<m;i++) c[i] += c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[S[i]]] = i;
rnk[sa[0]] = 0;
for(int i=1;i<n;i++) rnk[sa[i]] = rnk[sa[i-1]] + (S[sa[i]] != S[sa[i-1]]);
for(int k=1;rnk[sa[n-1]]!=n-1;k<<=1) {
int cnt = 0;
for(int i=n-k;i<n;i++) nsa[cnt++] = i;
for(int i=0;i<n;i++)
if( sa[i] >= k ) nsa[cnt++] = sa[i] - k;
for(int i=0;i<n;i++) nrnk[i] = rnk[i];
for(int i=0;i<n;i++) c[i] = 0;
for(int i=0;i<n;i++) c[nrnk[i]]++;
for(int i=1;i<n;i++) c[i] += c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[nrnk[nsa[i]]]] = nsa[i];
rnk[sa[0]] = 0;
for(int i=1;i<n;i++) rnk[sa[i]] = rnk[sa[i-1]] + (nrnk[sa[i]] != nrnk[sa[i-1]] || nrnk[sa[i]+k] != nrnk[sa[i-1]+k]);
}
}
int ht[MAXN + 5];
void get_height(int n) {
int k = 0;
for(int i=0;i<n;i++) {
if( rnk[i] == 0 ) ht[rnk[i]] = 0;
else {
if( k ) k--;
while( S[i+k] == S[sa[rnk[i]-1]+k] )
k++;
ht[rnk[i]] = k;
}
}
}
int st[20][MAXN + 5], lg[MAXN + 5];
void get_st(int n) {
for(int i=0;i<n;i++)
st[0][i] = ht[i];
for(int i=2;i<=n;i++)
lg[i] = lg[i>>1] + 1;
for(int j=1;j<20;j++) {
int t = (1<<(j-1));
for(int i=0;i+t<n;i++)
st[j][i] = min(st[j-1][i], st[j-1][i+t]);
}
}
int lcp(int l, int r) {
if( l == r ) return MAXN;
if( l > r ) swap(l, r); l++;
int k = lg[r-l+1], p = (1<<k);
return min(st[k][l], st[k][r-p+1]);
}
int ch[2][40*MAXN + 5], root, ncnt;
void link_edge(int rt, int l, int r, const int &ql, const int &qr, const int &x) {
if( l > qr || r < ql || (!rt) ) return ;
if( ql <= l && r <= qr ) {
addedge(x, rt + na + nb);
return ;
}
int mid = (l + r) >> 1;
link_edge(ch[0][rt], l, mid, ql, qr, x);
link_edge(ch[1][rt], mid + 1, r, ql, qr, x);
}
int insert(int rt, int l, int r, const int &p, const int &x) {
int q = (++ncnt);
ch[0][q] = ch[0][rt], ch[1][q] = ch[1][rt];
if( l == r ) {
if( rt ) addedge(q + na + nb, rt + na + nb);
addedge(q + na + nb, x);
}
else {
int mid = (l + r) >> 1;
if( p <= mid ) ch[0][q] = insert(ch[0][rt], l, mid, p, x);
else ch[1][q] = insert(ch[1][rt], mid + 1, r, p, x);
if( ch[0][q] ) addedge(q + na + nb, ch[0][q] + na + nb);
if( ch[1][q] ) addedge(q + na + nb, ch[1][q] + na + nb);
}
return q;
}
void get_lr(int ps, int len, int &l, int &r, const int &n) {
int le, ri;
le = rnk[ps], ri = n - 1;
while( le < ri ) {
int mid = (le + ri + 1) >> 1;
if( lcp(rnk[ps], mid) >= len ) le = mid;
else ri = mid - 1;
}
r = le;
le = 0, ri = rnk[ps];
while( le < ri ) {
int mid = (le + ri) >> 1;
if( lcp(rnk[ps], mid) >= len ) ri = mid;
else le = mid + 1;
}
l = ri;
}
long long dp[45*MAXN + 5];
int val[MAXN + 5], que[45*MAXN + 5], s, t;
long long tsort() {
long long ret = 0; s = 1, t = 0;
for(int i=1;i<=ncnt+na+nb;i++) {
if( !ind[i] ) que[++t] = i;
dp[i] = 0;
}
while( s <= t ) {
int f = que[s++];
if( f <= na ) dp[f] += val[f];
ret = max(ret, dp[f]);
for(edge *p=adj[f];p;p=p->nxt) {
ind[p->to]--;
if( !ind[p->to] ) que[++t] = p->to;
dp[p->to] = max(dp[p->to], dp[f]);
}
}
if( t != ncnt + na + nb )
return -1;
else return ret;
}
void solve() {
scanf("%s", S), lenS = strlen(S), ecnt = &edges[0];
get_sa(lenS + 1, 128);
get_height(lenS + 1);
get_st(lenS + 1);
scanf("%d", &na);
for(int i=1;i<=na;i++)
scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i, val[i] = a[i].len();
sort(a + 1, a + na + 1);
scanf("%d", &nb);
for(int i=1;i<=nb;i++)
scanf("%d%d", &b[i].l, &b[i].r), b[i].id = i;
sort(b + 1, b + nb + 1);
int p = na, q = nb; root = ncnt = 0;
while( p >= 1 && q >= 1 ) {
if( a[p].len() >= b[q].len() )
root = insert(root, 1, lenS, rnk[a[p].l-1], a[p].id), p--;
else {
int l, r; get_lr(b[q].l-1, b[q].len(), l, r, lenS + 1);
link_edge(root, 1, lenS, l, r, b[q].id + na), q--;
}
}
while( q >= 1 ) {
int l, r; get_lr(b[q].l-1, b[q].len(), l, r, lenS + 1);
link_edge(root, 1, lenS, l, r, b[q].id + na), q--;
}
scanf("%d", &m);
for(int i=1;i<=m;i++) {
int x, y; scanf("%d%d", &x, &y);
addedge(x, y + na);
}
printf("%lld\n", tsort());
for(int i=1;i<=na+nb+ncnt;i++)
adj[i] = NULL, ind[i] = 0;
}
int main() {
int T; scanf("%d", &T);
while( T-- ) solve();
}@details@
注意一个区间在线段树中会被拆成 2*logn 个结点而不是 logn 的结点。
虽然都是 O(logn)，但是开数组的时候不注意一下就可能会 RE。