洛谷 6292 区间本质不同子串个数

发表于 | 分类于 | 11

某种意义上第一道 LCT？（

考虑类比区间数颜色的做法，将询问离线按右端点排序，逐次考虑每个 [1,r] 的前缀。
对后缀自动机上每个状态 p 维护当前的 maxendpos(p)，那么每个字符串 S 对 l∈[1,maxendpos(S)−|S|+1] 的询问有贡献。

问题在于如何维护 maxendpos(p)，设这个东西为 last(p)，那么从 r−1 转移到 r 相当于修改 Parent Tree 上一条从根开始的链所有状态的 last 值为 r。
如果只要维护 last 值还好，可以直接上树链剖分 + 区间赋值的线段树。
然而我们同时要维护贡献，这就不大妙了。

注意到修改的是从根开始的一条链，这启发我们联想 LCT 的 Access 操作。
发现每条实链上的 last 值是相等的，并且所代表的长度是连续的，又相当于 S1…r 连续的一段后缀。
所以在合并实链的时候直接更新贡献。

此外，贡献实际上是区间加等差数列，单点查询，可以通过差分序列转化为区间加常数，区间查询，然后用 BIT 维护。

根据 LCT 的复杂度，容易发现这是 O(nlog2n) 的。
实现基本参考了 Fuyuki 大佬的代码。

代码： 

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
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int M = 2e5;
int n,m,ed[N + 5];
char s[N + 5];
vector< pair<int,int> > qry[N + 5];
long long ans[M + 5];
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    inline void insert(int x)
    {
        int p = ++tot,cur = las;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
}
namespace BIT
{
    #define lowbit(x) ((x) & -(x))
    long long c1[N + 5],c2[N + 5];
    inline void update(int x,int k)
    {
        for(register int i = x;i <= n;i += lowbit(i))
            c1[i] += k,c2[i] += x * k;
    }
    inline long long query(int x)
    {
        long long ret = 0;
        for(register int i = x;i;i -= lowbit(i))
            ret += (x + 1) * c1[i] - c2[i];
        return ret;
    }
    inline void update(int l,int r,int k)
    {
        update(l,k),update(r + 1,-k);
    }
    inline long long query(int l,int r)
    {
        return query(r) - query(l - 1);
    }
}
namespace LCT
{
    struct node
    {
        int fa,len,min;
        int las,tag;
        int ch[2];
    } tr[(N << 1) + 5];
    #define chk(p) (tr[tr[p].fa].ch[1] == p)
    #define is_son(p) (tr[tr[p].fa].ch[chk(p)] == p)
    inline void up(int p)
    {
        tr[p].min = min(tr[p].len,min(tr[tr[p].ch[0]].min,tr[tr[p].ch[1]].min));
    }
    inline void down(int p)
    {
        if(tr[p].tag)
            tr[tr[p].ch[0]].las = tr[tr[p].ch[0]].tag = tr[p].tag,
            tr[tr[p].ch[1]].las = tr[tr[p].ch[1]].tag = tr[p].tag,
            tr[p].tag = 0;
    }
    inline void rotate(int p)
    {
        int x = tr[p].fa,y = tr[x].fa,d = chk(p),t = tr[p].ch[d ^ 1];
        is_son(x) && (tr[y].ch[chk(x)] = p,1),
        tr[p].ch[d ^ 1] = x,tr[x].ch[d] = t,
        t && (tr[t].fa = x),
        tr[x].fa = p,tr[p].fa = y,
        up(x),up(p);
    }
    inline void splay(int p)
    {
        static int s[N + 5];
        int top = 0;
        s[++top] = p;
        for(register int x = p;is_son(x);s[++top] = x = tr[x].fa);
        for(;top;down(s[top--]));
        for(register int x;is_son(p);rotate(p))
            x = tr[p].fa,
            is_son(x) && (rotate((chk(p) ^ chk(x)) ? p : x),1);
    }
    inline void access(int p,int pos)
    {
        for(register int cur = p,x = 0;cur;cur = tr[x = cur].fa)
            splay(cur),tr[cur].ch[1] = x,up(cur),
            tr[cur].las && (BIT::update(tr[cur].las - SAM::sam[cur].len + 1,tr[cur].las - tr[cur].min + 1,-1),1);
        splay(p),tr[p].las = tr[p].tag = pos,BIT::update(pos - SAM::sam[p].len + 1,pos,1);
    }
    inline void init()
    {
        tr[0].min = 0x3f3f3f3f;
        for(register int i = 1;i <= SAM::tot;++i)
            tr[i].min = tr[i].len = SAM::sam[tr[i].fa = SAM::sam[i].fa].len + 1;
    }
}
int main()
{
    scanf("%s%d",s + 1,&m),n = strlen(s + 1);
    for(register int i = 1;i <= n;++i)
        SAM::insert(s[i] - 'a'),ed[i] = SAM::las;
    LCT::init();
    int l,r;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&l,&r),qry[r].push_back(make_pair(l,i));
    for(register int i = 1;i <= n;++i)
    {
        LCT::access(ed[i],i);
        for(register vector< pair<int,int> >::iterator it = qry[i].begin();it != qry[i].end();++it)
            ans[it->second] = BIT::query(it->first,i);
    }
    for(register int i = 1;i <= m;++i)
        printf("%lld\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment