Codeforces 587F Duff is Mad

发表于 | 分类于 | 6

无内鬼，来一发和 ACAM 解法并无本质区别的 SAM 解法（

首先把询问差分成两个参数 r,k，并考虑两个子问题：

  1. 若每次询问的 |sk| 之和较小。

    将询问对 r 排序，在 Parent Tree 上把每个 si (i≤r) 对应的状态的子树加一，枚举 sk 每个前缀对应的状态并求和。
    相当于反向统计 |endpos| 之和 —— 计算每个结束位置上有多少串造成贡献。

  2. 若 q 较小。

    将所有 sk 的每个前缀对应的状态在 Parent Tree 上加一，并求子树和，即求每个状态在每个 sk 中的的 |endpos|。
    同样将询问对 r 排序，对每个 si (i≤r) 对应的状态求其在 sk 中的 |endpos| 之和。

考虑设一个阈值 T，若询问的 |sk|≤T，则做第一个子问题，否则做第二个子问题。
若忽略第一个子问题中数据结构的复杂度，两部分复杂度分别为 O(nT+n2T)（假设 n,q,∑|si| 同阶）。
显然当 T=O(√n) 时取最优复杂度 O(n√n)。

再来考虑第一个子问题中的数据结构，注意到共有 O(n) 次修改和 O(n√n) 次查询，使用分块做到 O(√n) 单次修改和 O(1) 单次查询即可。
总复杂度依然为 O(n√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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int LIM = 430;
const int CNT = N / LIM + 2;
int n,m,m_lim,q,lim = LIM;
int len[N + 5],slen[N + 5],ed[N + 5];
int vis[N + 5],cnt;
char s[N + 5];
long long sum[CNT + 5],ans[N + 5];
struct s_query
{
    int r,k,w,id;
    inline bool operator<(const s_query &o) const
    {
        return r < o.r;
    }
} qry[(N << 1) + 5],qry_lim[(N << 1) + 5];
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    int sz[(N << 1) + 5][CNT + 5];
    inline void insert(int x)
    {
        if(sam[las].ch[x])
        {
            int cur = las,q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                las = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
                las = nxt;
            }
            return ;
        }
        int cur = las,p = ++tot;
        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;
    }
    inline void build()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= N;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            for(register int j = 1;j <= cnt;++j)
                sz[sam[a[i]].fa][j] += sz[a[i]][j];
    }
}
namespace BLOCK
{
    const int N = 2e5;
    const int BLK = 450;
    const int CNT = N / BLK + 2;
    int n,block = BLK,pos[N + 5];
    int pre[CNT + 5],sum[N + 5];
    inline void init()
    {
        n = SAM::tot;
        for(register int i = 1;i <= n;++i)
            pos[i] = (i - 1) / block + 1;
    }
    inline void update(int x,int k)
    {
        if(x > n)
            return ;
        for(register int i = pos[x];i <= pos[n];++i)
            pre[i] += k;
        for(register int i = x;i <= min(pos[x] * block,n);++i)
            sum[i] += k;
    }
    inline void update(int l,int r,int k)
    {
        update(l,k),update(r + 1,-k);
    }
    inline int query(int x)
    {
        return pre[pos[x] - 1] + sum[x];
    }
}
namespace TREE
{
    int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
    inline void add(int u,int v)
    {
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    int sz[(N << 1) + 5],id[(N << 1) + 5];
    void dfs(int p)
    {
        static int tot = 0;
        id[p] = ++tot,sz[p] = 1;
        for(register int i = first[p];i;i = pre[i])
            dfs(to[i]),sz[p] += sz[to[i]];
    }
    inline void init()
    {
        for(register int i = 2;i <= SAM::tot;++i)
            add(SAM::sam[i].fa,i);
        dfs(1);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(register int i = 1;i <= n;++i)
        scanf("%s",s + slen[i - 1] + 1),slen[i] = slen[i - 1] + (len[i] = strlen(s + slen[i - 1] + 1));
    for(register int i = 1;i <= n;++i)
    {
        len[i] > lim && (vis[i] = ++cnt),SAM::las = 1;
        for(register int j = 1;j <= len[i];++j)
            SAM::insert(s[slen[i - 1] + j] - 'a'),ed[slen[i - 1] + j] = SAM::las,vis[i] && ++SAM::sz[SAM::las][cnt];
    }
    SAM::build(),BLOCK::init(),TREE::init();
    int l,r,k;
    for(register int i = 1;i <= q;++i)
    {
        scanf("%d%d%d",&l,&r,&k);
        if(vis[k])
            qry_lim[++m_lim] = (s_query){r,vis[k],1,i},qry_lim[++m_lim] = (s_query){l - 1,vis[k],-1,i};
        else
            qry[++m] = (s_query){r,k,1,i},qry[++m] = (s_query){l - 1,k,-1,i};
    }
    sort(qry + 1,qry + m + 1),sort(qry_lim + 1,qry_lim + m_lim + 1);
    for(register int i = 1,r = 1;i <= m;++i)
    {
        for(;r <= qry[i].r;++r)
            BLOCK::update(TREE::id[ed[slen[r]]],TREE::id[ed[slen[r]]] + TREE::sz[ed[slen[r]]] - 1,1);
        for(register int j = 1;j <= len[qry[i].k];++j)
            ans[qry[i].id] += qry[i].w * BLOCK::query(TREE::id[ed[slen[qry[i].k - 1] + j]]);
    }
    for(register int i = 1,r = 1;i <= m_lim;++i)
    {
        for(;r <= qry_lim[i].r;++r)
            for(register int j = 1;j <= cnt;++j)
                sum[j] += SAM::sz[ed[slen[r]]][j];
        ans[qry_lim[i].id] += qry_lim[i].w * sum[qry_lim[i].k];
    }
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment