@loj - 3049@ 「十二省联考 2019」字符串问题

目录


@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。

上一篇:NA公链(Nirvana)NAC公链独步公链江湖


下一篇:R语言多列均值计算,单因素logistic分析