【题解】HDU-6054-String and String

Posted on In Disqus:

题目

http://acm.hdu.edu.cn/showproblem.php?pid=6054

题意

  • 有两个字符串 T 和 S
  • S 的每个位置有一个权值 f[i]。
  • 强制在线，两种操作：
    • 将 f[x] 修改为 v。
    • 对于 T 的某一个子串在 S 的某一个子串中匹配，求出所有匹配位置的终点的 f 的和。

题解

  • 2017 多校的题，时隔半年之久，终于在我的能力范围内了。
  • 对 S 和 T 建立广义后缀自动机。
  • 为了快速得到 T 的一个子串对应的状态，在后缀自动机得到的后缀树上预处理倍增。
  • 某个状态的所有匹配位置是该状态子树中所有关键点的匹配位置的并，也就是求子树中所有匹配位置在某个范围内的 f 的和。
  • 采用树状数组套主席树来维护 dfs 序上的 f 的值。
  • 为了节省一些运行时间和内存，代码中采用了静态主席树 + 动态主席树（树状数组套主席树）。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int M = 4E5 + 100;
int f[M];
char s[M];
int ls, T, Q, ans;

namespace sam {
    int t[M][26], len[M] = {-1}, fa[M], sz, last, rpos[2][M], pos[2][M];
    void ins(int ch, int pp, int id) {
        int p = last, np = 0, nq = 0, q = -1;
        if (!t[p][ch]) {
            np = sz++;
            len[np] = len[p] + 1;
            for (; p && !t[p][ch]; p = fa[p]) t[p][ch] = np;
        }
        if (!p) fa[np] = 1;
        else {
            q = t[p][ch];
            if (len[p] + 1 == len[q]) fa[np] = q;
            else {
                nq = sz++; len[nq] = len[p] + 1;
                memcpy(t[nq], t[q], sizeof t[0]);
                fa[nq] = fa[q];
                fa[np] = fa[q] = nq;
                for (; t[p][ch] == q; p = fa[p]) t[p][ch] = nq;
            }
        }
        last = np ? np : nq ? nq : q;
        rpos[id][pp] = last; pos[id][last] = pp;
    }
}

const int SP = 19;
vector<int> G[M];
int in[M], out[M], pa[M][SP], clk, rin[M];
void dfs(int u, int fa) {
    in[u] = ++clk; rin[clk] = u;
    pa[u][0] = fa;
    FOR (i, 1, SP) pa[u][i] = pa[pa[u][i - 1]][i - 1];
    for (int& v: G[u]) dfs(v, u);
    out[u] = clk;
}

int go_up(int u, int l) {
    using namespace sam;
    FORD (i, SP - 1, -1) {
        int v = pa[u][i];
        if (len[u] - len[v] <= l) {
            l -= len[u] - len[v];
            u = v;
        }
    }
    return u;
}

namespace tree {
#define mid ((l + r) >> 1)
#define lson l, mid
#define rson mid + 1, r
    const int MAGIC = M * 30;
    struct P {
        int sum, ls, rs;
    } tr[MAGIC] = {{0, 0, 0}};
    int sz;
    int N(int sum, int ls, int rs) {
        if (sz == MAGIC) while(1);
        tr[sz] = {sum, ls, rs};
        return sz++;
    }
    int ins(int o, int x, int v, int l = 1, int r = ls) {
        if (x < l || x > r) return o;
        const P& t = tr[o];
        if (l == r) return N(t.sum + v, 0, 0);
        return N(t.sum + v, ins(t.ls, x, v, lson), ins(t.rs, x, v, rson));
    }
    int query(int o, int ql, int qr, int l = 1, int r = ls) {
        if (ql > r || l > qr) return 0;
        const P& t = tr[o];
        if (ql <= l && r <= qr) return t.sum;
        return query(t.ls, ql, qr, lson) + query(t.rs, ql, qr, rson);
    }
}

namespace bit {
    using namespace tree;
    int c[M];
    inline int lowbit(int x) { return x & -x; }
    void add(int p, int x, int v) {
        for (int i = p; i <= sam::sz; i += lowbit(i))
            c[i] = ins(c[i], x, v);
    }
    int sum(int p, int ql, int qr) {
        int ret = 0;
        for (int i = p; i > 0; i -= lowbit(i))
            ret += query(c[i], ql, qr);
        return ret;
    }
    inline int sum(int l, int r, int ql, int qr) {
        return sum(r, ql, qr) - sum(l - 1, ql, qr);
    }
}

void mod(int p, int v) {
    int u = in[sam::rpos[0][p]];
    bit::add(u, p + 1, v - f[p]); // + 1
    f[p] = v;
}

int old[M];
void q_init() {
    int o = 0;
    FOR (i, 1, sam::sz) {
        int u = rin[i], p = sam::pos[0][u];
        if (~p) o = tree::ins(o, p + 1, f[p]); // + 1
        old[i] = o;
    }
}

int query(int a, int b, int c, int d) {
    c += b - a;
    if (c > d) return 0;
    int u = go_up(sam::rpos[1][b], a);
    ++c; ++d; // + 1
    return bit::sum(in[u], out[u], c, d)
           + tree::query(old[out[u]], c, d) - tree::query(old[in[u] - 1], c, d);
}

void _init();
int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    using namespace sam;
    cin >> T;
    while (T--) {
        _init();
        scanf("%s", s); ls = strlen(s);
        FOR (i, 0, ls) ins(s[i] - 'a', i, 0);

        last = 1;
        scanf("%s", s);
        FOR (i, 0, strlen(s)) ins(s[i] - 'a', i, 1);

        FOR (i, 0, ls) scanf("%d", &f[i]);
        FOR (i, 2, sz) G[fa[i]].push_back(i);
        dfs(1, 0);
        q_init();

        cin >> Q;
        while (Q--) {
            int tp, a, b, c, d;
            scanf("%d", &tp);
            if (tp == 1) {
                scanf("%d%d", &a, &b);
#ifndef zerol
                a ^= ans; b ^= ans;
#endif
                mod(a, b);
            } else {
                scanf("%d%d%d%d", &a, &b, &c, &d);
#ifndef zerol
                a ^= ans; b ^= ans; c ^= ans; d ^= ans;
#endif
                ans = query(a, b, c, d);
                printf("%d\n", ans);
            }
        }
    }
}

void _init() {
    clk = 0;
    tree::sz = 1;
    memset(sam::t, 0, sizeof sam::t);
    memset(sam::pos, -1, sizeof sam::pos);
    sam::sz = 2;
    sam::last = 1;
    memset(bit::c, 0, sizeof bit::c);
    FOR (i, 0, M) G[i].clear();
}

/*
 * state [1, sz)
 * dfn [1, sz)
 * old [1, sz)
 * tree_range [1, len(s)] (+1 needed)
 * bit_range [1, sz)
 */

标程

官方题解链接

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=100001;
int lens;
namespace SAM{
const int Len=maxn*2,Alp=26;
int pa[Len<<1],son[Len<<1][Alp],Right[Len<<1],fR[Len<<1];
int Max[Len<<1],cnt,root,last;
inline int Newnode(int _Max){++cnt;memset(son[cnt],0,sizeof(son[cnt]));Max[cnt]=_Max;return cnt;}
inline void pre(){cnt=Max[0]=0;root=last=Newnode(0);}
inline void sam(int alp)
{
    int np=son[last][alp],u=last,v,nv;
    if(np&&Max[np]==Max[last]+1){last=np;return;}
    np=Newnode(Max[last]+1);
    Right[np]=Max[last];
    fR[Max[last]]=np;
    while(u&&!son[u][alp])son[u][alp]=np,u=pa[u];
    if(!u)pa[np]=root;
    else
    {
        v=son[u][alp];
        if(Max[v]==Max[u]+1)pa[np]=v;
        else
        {
            nv=Newnode(Max[u]+1);   Right[nv]=-1;
            memcpy(son[nv],son[v],sizeof(son[v]));
            pa[nv]=pa[v],pa[v]=pa[np]=nv;
            while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
        }
    }
    last=np;
}
char S[maxn*2+10];
vector<int>node[Len*2];
int dcnt=0,ls[Len*2],rs[Len*2],row[Len*2],fa[Len*2][19];
void predfs(int u)
{
	ls[u]=++dcnt;
	row[dcnt]=u;
	fa[u][0]=pa[u];
	for(int x=1;x<=18;x++)
		fa[u][x]=fa[fa[u][x-1]][x-1];
	for(auto& v:node[u])
		predfs(v);
	rs[u]=dcnt;
}
int test()
{
    pre();
    int len=strlen(S);
    for(int x=0;x<len;x++)
        {sam(S[x]-'a');}
	for(int x=0;x<=cnt;x++)node[x].clear();
	for(int x=0;x<=cnt;x++)
		node[pa[x]].pb(x);
	dcnt=0;
	predfs(1);
	Max[0]=-1;
    return len;
}
}

namespace tree{
int root[maxn*2],cnt,f[maxn];
const int magic1=maxn*20;
struct node{int l,r,sum;}tr[magic1];
void update(int l,int r,int x,int &y,int pos,int val)       //(l,r,root[x],root[x+1],pos)
{
	if(cnt+1>magic1-10){puts("tree");while(1);}
    tr[++cnt]=tr[x],tr[cnt].sum+=val,y=cnt;
    if(l==r)return;
    int mid=(l+r)/2;
    if(mid>=pos)update(l,mid,tr[x].l,tr[y].l,pos,val);
    else update(mid+1,r,tr[x].r,tr[y].r,pos,val);
}
int query(int l,int r,int x,int pos)
{
	if(pos<0)return 0;
    if(l==r)return tr[x].sum;
    int mid=(l+r)/2;
    if(mid>=pos)return query(l,mid,tr[x].l,pos);
    else return tr[tr[x].l].sum+query(mid+1,r,tr[x].r,pos);
}
}

namespace bit{
int root[maxn*4],cnt,len;
const int magic2=maxn*30;
struct node{int l,r,sum;}tr[magic2];
int newnode(){++cnt;tr[cnt].l=tr[cnt].r=tr[cnt].sum=0;return cnt;}
void update(int l,int r,int x,int pos,int val)
{
	if(cnt>magic2-10){puts("bit");while(1);}
    tr[x].sum+=val;
    if(l==r)return;
    int mid=(l+r)/2;
    if(mid>=pos){if(tr[x].l==0)tr[x].l=newnode();update(l,mid,tr[x].l,pos,val);}
    else{if(tr[x].r==0)tr[x].r=newnode();update(mid+1,r,tr[x].r,pos,val);}
}
int query(int l,int r,int x,int pos)
{
	if(pos<0)return 0;
    if(l==r)return tr[x].sum;
    int mid=(l+r)/2;
    if(mid>=pos)return query(l,mid,tr[x].l,pos);
    else return tr[tr[x].l].sum+query(mid+1,r,tr[x].r,pos);
}
void change(int a,int b)
{
	int t=b-tree::f[a];
	tree::f[a]=b;
	for (int x=SAM::ls[SAM::fR[a]]; x&&x<=len; x+=x&-x)
	{
		update(0,lens-1,root[x],a,t);
	}
}
int queryr(int a, int b, int c, int d)
{
	int ans=0;
    for (int x=b; x; x^=x&-x)
		ans+=query(0,lens-1,root[x],d)-query(0,lens-1,root[x],c-1);
	for (int x=a-1; x; x^=x&-x)
		ans-=query(0,lens-1,root[x],d)-query(0,lens-1,root[x],c-1);
    return ans;
}
}

int query(int A,int B,int C,int D)
{
	int t=SAM::fR[B],len=B-A+1;
	for(int x=18;x>=0;x--)
		if(len<=SAM::Max[SAM::fa[t][x]])
			t=SAM::fa[t][x];
	int a=SAM::ls[t],b=SAM::rs[t];
	int c=C+len-1,d=D;
	if(c>d)return 0;

    int ans=bit::queryr(a,b,c,d)+
    (tree::query(0,lens-1,tree::root[b],d)-tree::query(0,lens-1,tree::root[b],c-1))
    -(tree::query(0,lens-1,tree::root[a-1],d)-tree::query(0,lens-1,tree::root[a-1],c-1));

    return ans;
}
int main()
{
    //freopen("true_in.txt", "r", stdin);
    //freopen("out2.txt", "w", stdout);
	int size = 256 << 20; // 256MB
	char *pp = (char*)malloc(size) + size;
	//__asm__("movl %0, %%esp\n" :: "r"(pp));
	int CASE;
	scanf("%d",&CASE);
	while(CASE--)
	{
    scanf("%s",SAM::S);
    lens=strlen(SAM::S);
    scanf("%s",SAM::S+lens);
    SAM::test();
    bit::len=SAM::cnt;
    for(int x=0;x<lens;x++)
		scanf("%d",&tree::f[x]);
	tree::cnt=0;
	tree::root[0]=tree::root[1]=tree::tr[0].l=tree::tr[0].r=tree::tr[0].sum=0;
	for(int x=2;x<=SAM::dcnt;x++)
		if(SAM::Right[SAM::row[x]]<lens&&SAM::Right[SAM::row[x]]!=-1)
			tree::update(0,lens-1,tree::root[x-1],tree::root[x],SAM::Right[SAM::row[x]],tree::f[SAM::Right[SAM::row[x]]]);
		else
			tree::root[x]=tree::root[x-1];
	int qu;
	scanf("%d",&qu);
	bit::cnt=0;
	bit::tr[0].l=bit::tr[0].r=bit::tr[0].sum=0;
	for(int x=1;x<=bit::len;x++)
		bit::root[x]=bit::newnode();
	int ans=0;
	for(int x=1;x<=qu;x++)
	{
		int t;
		scanf("%d",&t);
		if(t==1)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			a^=ans;b^=ans;
			bit::change(a,b);
		}
		else if(t==2)
		{
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			a^=ans;b^=ans;c^=ans;d^=ans;
			if(b-a>d-c)
				ans=0;
			else
				ans=query(a+lens,b+lens,c,d);
			printf("%d\n",ans);
		}
	}
	}
    return 0;
}