String and String

Posted on | In , ,

题目链接

题意

输入两个字符串$s$,$t$，且$S$串每个位置有权值$f(i)$，定义$Sval$为$S$串（所有匹配$T$串某一个位置）的子串的右端点权值的和。$q$次操作：
1.把 改为。

2.询问$T$子串的$Sval$。

思路

这题理解了好久，可能还没理解透彻。先整理下思路，后面更新代码。
总的来说是一道码量惊人的题目。

后缀自动机

实现匹配，我们很容易想到后缀自动机，首先将$S$拼接在$T$后面（反过来也行），建出的后缀自动机，但是由于这题权值定义为右端点，如果用后缀去搞，我们明显更容易确定左端点，所以我们在建串的时候先把两个串反过来。
那么能够匹配$T$串某一个子串的$S$串起始位置在后缀树组上其实是一段连续的区间，我们现在要求的其实就是这段区间里其实位置在$S$串要求范围里的$f$值。

RMQ

首先我们来看一下怎么找这个区间，利用后缀数组，我们可以知道两个不同位置开始的后缀的$lcp$，我们可以在上面两次二分，找出最大的能够匹配整个要求的$T$子串的范围。怎么check呢？回想我们以前后缀数组的套路，无非就是RMQ一下，看看整个区间是不是height最小值大于等于我们要的长度。

树套数

我们现在已经利用RMQ知道了这个后缀数组中的区间在哪里，现在要做的就是求和。
也就是
如果只是普通求$f$和我们一个线段树或树状数组就可以解决，现在还有一维范围要求，那么我们可以树套数解决这个问题。
树状数组的每个点都是一棵线段树，按照sa的顺序往线段树里面加点，这样就可以求出一个后缀数组区间里指定范围内的权值和。

蔡队代码，具体可见wiki

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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <bits/stdc++.h>
using std::min;
using std::printf;
using std::reverse;
using std::scanf;
using std::swap;

const int maxn = 1 << 19;
namespace Suffix_Array
{
char s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], rank[maxn], height[maxn];
void build_sa(int m, int n)
{
    n++;
    int *x = t, *y = t2;
    for (int i = 0; i < m; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
    for (int i = 1; i < m; i++) c[i] += c[i - 1];
    for (int i = n - 1; ~i; i--) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int p = 0;
        for (int i = n - k; i < n; i++) y[p++] = i;
        for (int i = 0; i < n; i++)
            if (sa[i] >= k) y[p++] = sa[i] - k;
        for (int i = 0; i < m; i++) c[i] = 0;
        for (int i = 0; i < n; i++) c[x[y[i]]]++;
        for (int i = 1; i < m; i++) c[i] += c[i - 1];
        for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n) break;
        m = p;
    }
    n--;
    int k = 0;
    for (int i = 0; i <= n; i++) rank[sa[i]] = i;
    for (int i = 0; i < n; i++)
    {
        if (k) k--;
        int j = sa[rank[i] - 1];
        while (s[i + k] == s[j + k]) k++;
        height[rank[i]] = k;
    }
}

int dp[maxn][30];
void initrmq(int n)
{
    for (int i = 1; i <= n; i++)
        dp[i][0] = height[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq(int l, int r)
{
    int k = 31 - __builtin_clz(r - l + 1);
    return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int lcp(int a, int b)
{
    a = rank[a], b = rank[b];
    if (a > b) swap(a, b);
    return rmq(a + 1, b);
}
} // namespace Suffix_Array
using Suffix_Array::build_sa;
using Suffix_Array::initrmq;
using Suffix_Array::lcp;
using Suffix_Array::rank;
using Suffix_Array::rmq;
using Suffix_Array::sa;

namespace BIT
{
int n, m;
int root[maxn], lson[maxn << 4], rson[maxn << 4], sum[maxn << 4], sz;
void init(int n, int m)
{
    BIT::n = n, BIT::m = m;
    for (int i = 0; i <= n; i++) root[i] = -1;
    sz = 0;
}
#define Lson l, m, lson[o]
#define Rson m + 1, r, rson[o]
void update(int p, int v, int l, int r, int& o)
{
    if (!~o) o = sz++, sum[o] = 0, lson[o] = -1, rson[o] = -1;
    assert(sz < (maxn << 4));
    sum[o] += v;
    if (l == r) return;
    const int m = l + r >> 1;
    if (p <= m)
        update(p, v, Lson);
    else
        update(p, v, Rson);
}
int query(int L, int R, int l, int r, int o)
{
    if (!~o) return 0;
    if (L <= l && r <= R) return sum[o];
    const int m = l + r >> 1;
    int ret = 0;
    if (L <= m) ret += query(L, R, Lson);
    if (m < R) ret += query(L, R, Rson);
    return ret;
}
void update(int x, int p, int v)
{
    for (int i = x; i <= n; i += i & -i) update(p, v, 0, m, root[i]);
}
int query(int L, int R, int l, int r)
{
    int ret = 0;
    for (int i = R; i; i -= i & -i) ret += query(l, r, 0, m, root[i]);
    for (int i = L - 1; i; i -= i & -i) ret -= query(l, r, 0, m, root[i]);
    return ret;
}
} // namespace BIT

char s[maxn], t[maxn];
int f[maxn];
int ans;
inline void decode(int& a) { a ^= ans; }

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ans = 0;
        scanf("%s%s", s, t);
        int n = strlen(s), m = strlen(t);
        reverse(s, s + n), reverse(t, t + m);
        for (int i = 0; s[i]; i++) scanf("%d", f + i);
        reverse(f, f + n);
        int sz = 0;
        for (int i = 0; s[i]; i++) Suffix_Array::s[sz++] = s[i];
        Suffix_Array::s[sz++] = '$';
        for (int i = 0; t[i]; i++) Suffix_Array::s[sz++] = t[i];
        Suffix_Array::s[sz] = 0;
        assert(sz == n + m + 1);
        build_sa(128, sz);
        initrmq(sz);
        BIT::init(sz, n - 1);
        for (int i = 1; i <= sz; i++)
            if (sa[i] < n) BIT::update(i, sa[i], f[sa[i]]);
        int q;
        scanf("%d", &q);
        while (q--)
        {
            static int op, a, b, c, d;
            scanf("%d", &op);
            if (op == 1)
            {
                scanf("%d%d", &a, &b);
                decode(a), decode(b);
                a = n - a - 1;
                assert(a < n && a >= 0);
                BIT::update(rank[a], a, b - f[a]);
                f[a] = b;
            }
            else if (op == 2)
            {
                scanf("%d%d%d%d", &c, &d, &a, &b);
                decode(a), decode(b), decode(c), decode(d);
                a = n - 1 - a, b = n - 1 - b, c = m - c + n, d = m - d + n;
                swap(a, b), swap(c, d);
                int l = 1, r = rank[c] - 1;
                int lb = rank[c], ub = rank[c];
                while (l <= r)
                {
                    int m = l + r >> 1;
                    if (rmq(m + 1, rank[c]) >= d - c + 1)
                        lb = m, r = m - 1;
                    else
                        l = m + 1;
                }
                l = rank[c] + 1, r = sz;
                while (l <= r)
                {
                    int m = l + r >> 1;
                    if (rmq(rank[c] + 1, m) >= d - c + 1)
                        ub = m, l = m + 1;
                    else
                        r = m - 1;
                }
                b = b - d + c;
                if (a > b)
                    ans = 0;
                else
                    ans = BIT::query(lb, ub, a, b);
                printf("%d\n", ans);
            }
            else
                assert(false);
        }
    }
}
0%