DDOSvoid's Blog

Luogu P6292 区间本质不同子串个数

发表于 分类于
本文字数： 4.6k 阅读时长 ≈ 4 分钟

题目描述

https://www.luogu.com.cn/problem/P6292

简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次询问，每次询问给定区间 $[l,r]$，求 $S[l..r]$ 有多少本质不同的子串

$n\le 10^5,m\le 2\times 10^5$

Solution

我们首先考虑一个弱化的问题，每次求结束位置在 $[l,r]$ 的本质不同的子串，我们对 $S$ 建立后缀自动机，然后我们找到 $1$ 到 $n$ 所对应的 $n$ 个 $np$ 节点，那么区间 $[l,r]$ 的查询相当于是查询 $[l,r]$ 的 $np$ 节点在 $parent$ 树上树链的并，对于这个问题我们还是考虑离线，我们考虑做扫描线，将树上每个节点的值挂在子树内最大 $np$ 节点上，那么每次查询相当于是区间查询，每次修改相当于是将一个点到根的路径上的所有节点重新染色，注意到对于同一个颜色段的操作相同，而且这个操作即是 $LCT$ 的 $access$ 操作，所以我们可以用 $LCT$ 维护同色链，用树状数组维护权值，总时间复杂度 $O(n\log^2 n+m\log n)$

然后我们回到这个问题，我们现在的限制不只是结束位置在 $[l,r]$，还要保证起始位置也在 $[l,r]$，但其实操作类似，对于 $parent$ 树上的点，不妨设这个点所表示的串长在 $[a,b]$ 以及当前扫描线扫到 $r$，我们只需要将这个点的每个串的贡献挂在 $[r-a+1,r-b+1]$ 即可，同时在 $parent$ 树上，树链所表示的串长是一个连续区间，可以维护，那么我们现在每次修改相当于是区间加等差数列单点查询，我们可以将其转换成区间加区间查询，这样我们仍然可以使用树状数组来维护，时间复杂度 $O(n\log^2 n+m\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxn 100010
#define Maxn 200010
#define maxm 200010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, a[maxn];
char s[maxn];

namespace Bit {
    ll B1[maxn], B2[maxn];
    
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))
            B1[i] += v, B2[i] += x * v;
    }
    ll get_sum(int x) {
        ll s = 0;
        for (int i = x; i; i -= lowbit(i))
            s += (x + 1) * B1[i], s -= B2[i];
        return s; 
    }
    void update(int l, int r, int v) { add(l, v); add(r + 1, -v); }
    ll query(int l, int r) { return get_sum(r) - get_sum(l - 1); } 
}

namespace SAM { 
    struct node {
        int sz, L, l, nxt[26]; 
    } T[Maxn]; int f[Maxn], top, last, rt;
    void init() {
        for (int i = 1; i <= top; ++i) {
            T[i].sz = T[i].L = T[i].l = f[i] = 0; 
            fill(T[i].nxt, T[i].nxt + 26, 0); 
        }
        rt = last = top = 1; 
        T[rt].L = T[rt].l = f[rt] = 0;
    }
    void extend(int ch, int k) {
        int np = ++top, p = last; last = np;
        T[np].L = T[p].L + 1; a[k] = np; 
        while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
        if (!p) return f[np] = rt, void();
        int q = T[p].nxt[ch];
        if (T[q].L - 1 == T[p].L) f[np] = q;
        else {
            int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
            for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
            while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
            f[np] = f[q] = nq;
        } 
    }
    int tax[maxn], tp[Maxn]; 
    void rsort(int n) {
        for (int i = 1; i <= n; ++i) tax[i] = 0; 
        for (int i = 1; i <= top; ++i) ++tax[T[i].L];
        for (int i = 1; i <= n; ++i) tax[i] += tax[i - 1];
        for (int i = 1; i <= top; ++i) tp[tax[T[i].L]--] = i;
        for (int i = top, u = tp[i]; i > 1; u = tp[--i]) T[u].l = T[f[u]].L + 1;
    }
}

namespace LCT {
#define lc T[i].ch[0]
#define rc T[i].ch[1]
    struct LinkCutTree {
        int vmn, vmx, valmn, valmx, ch[2];
        bool rev; int c;
    } T[Maxn]; int f[Maxn];
    void init(int n) {
        T[0].vmn = 1e9; T[0].vmx = 0;
        for (int i = 1; i <= n; ++i) {
            T[i].valmn = T[i].vmn = SAM::T[i].l;
            T[i].valmx = T[i].vmx = SAM::T[i].L;
            f[i] = SAM::f[i];
        }
        T[1].valmn = T[1].vmn = 1e9;
        T[1].valmx = T[1].vmx = 0;
    }
    inline int get(int i) {
        if (T[f[i]].ch[0] == i) return 0;
        if (T[f[i]].ch[1] == i) return 1;
        return -1;
    }
    inline void maintain(int i) { 
        T[i].vmn = min({ T[i].valmn, T[lc].vmn, T[rc].vmn });
        T[i].vmx = max({ T[i].valmx, T[lc].vmx, T[rc].vmx });
    }
    inline void setc(int i, int c) {
        if (!i) return ;
        T[i].c = c;
    }
    inline void setr(int i) { 
        if (!i) return ;
        T[i].rev ^= 1; swap(lc, rc); 
    }
    inline void push(int i) {
        bool &rev = T[i].rev; int &c = T[i].c;
        if (rev) setr(lc), setr(rc);
        setc(lc, c), setc(rc, c); 
        rev = 0;
    }
    inline void rotate(int x) {
        int fa = f[x], ffa = f[f[x]], wx = get(x);
        if (~get(fa)) T[ffa].ch[T[ffa].ch[1] == fa] = x;
        f[x] = ffa; f[fa] = x; f[T[x].ch[wx ^ 1]] = fa;
        T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
        maintain(fa); maintain(x); 
    } 
    void clt(int i) {
        static int st[maxn], top;
        st[top = 1] = i; 
        while (~get(i)) st[++top] = i = f[i];
        while (top) push(st[top--]); 
    }
    void Splay(int i) {
        clt(i);
        for (int fa = f[i]; ~get(i); rotate(i), fa = f[i])
            if (~get(fa)) rotate(get(i) == get(fa) ? fa : i);
    }
    void access(int i, int c) {
        for (int p = 0; i; i = f[p = i]) {
            Splay(i); 
            rc = 0, maintain(i);
            if (T[i].c && i != 1) Bit::update(T[i].c - T[i].vmx + 1, T[i].c - T[i].vmn + 1, -1); 
            T[i].c = c, rc = p, maintain(i);
        }
    }
}

vector<pair<int, int>> A[maxn];
ll ans[maxm];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1 >> m; n = strlen(s + 1); SAM::init();
    for (int i = 1; i <= n; ++i) SAM::extend(s[i] - 'a', i);
    SAM::rsort(n); LCT::init(SAM::top);
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        A[y].emplace_back(x, i); 
    }
    for (int i = 1; i <= n; ++i) {
        LCT::access(a[i], i); Bit::update(1, i, 1); 
        for (auto [l, id] : A[i]) ans[id] = Bit::query(l, i); 
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}