BZOJ2555 Substring

发表于

  题意:一个字符串，两种操作，强制在线:

  1、在当前字符串后接上一个字符串

  2、查询某一串在当前字符串的出现次数

  维护每一个子串的出现次数，很容易想到SAM维护right集合大小。在SAM上运行这个串，在next边形成的树结构中，到达节点为根的子树的节点个数就是答案。
  暴力做法自然就是每次新加入一个字符，沿着next边向上更新节点信息。鉴于这是一个树结构，我们考虑用动态树来加速。
  但是好像要维护子树大小?虽然这样可做，但是有没有更简洁的方法?我们注意到这道题是没有换根操作的，树本身的形态不会改变，于是我们可以类似与暴力，将子树大小当做信息记在节点上。每次连next边的时候cut、link一下改变树的形态，暴力更新信息变成打tag就好。由于节点信息是独立的，所以连pushup都不要。注意每次在复制、输出节点信息时别忘了relax一波。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <ctime>
 
using namespace std;
 
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define mp make_pair
#define ms(a, b) memset(a, b, sizeof a)
 
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
    if(flag) x = -x; return x;
}
 
const int SIZE = 1500010, SIGMA = 26;
 
int q, mask, ans;
 
struct node
{
    node *p, *c[2];
    bool rev;
    int val, add;
 
    node(): p(0), rev(0), val(0), add(0) { c[0] = c[1] = 0; }
 
    void setc(node* o, bool b) { c[b] = o; if(o) o->p = this; }
 
    bool isroot() { return !p || p->c[0] != this && p->c[1] != this; }
 
    bool getpos() { return p->c[1] == this; }
 
    void updrev() { rev ^= 1; }
 
    void pushdown()
    {
        if(rev)
        {
            rep(i, 0, 1) if(c[i]) c[i]->updrev();
            swap(c[0], c[1]); rev ^= 1;
        }
 
        if(add)
        {
            rep(i, 0, 1) if(c[i])
            {
                c[i]->val += add;
                c[i]->add += add;
            }
            add = 0;
        }
    }
 
    void rot()
    {
        node* f = p; bool b = getpos();
        if(f->isroot()) p = f->p;
        else f->p->setc(this, f->getpos());
        f->setc(c[!b], b); setc(f, !b);
    }
 
    void relax() { if(!isroot()) p->relax(); pushdown(); }
 
    void splay()
    {
        for(relax(); !isroot(); rot())
            if(!p->isroot()) (p->getpos() == getpos() ? p : this)->rot();
    }
 
    void access()
    {
        for(node *u = this, *v = 0; u; v = u, u = u->p)
            u->splay(), u->setc(v, 1);
        splay();
    }
}nd[SIZE];
 
namespace LCT
{
    void cut(int x)
    {
        node* u = nd + x;
        u->access(); u->c[0] = u->c[0]->p = NULL;
    }
 
    void link(int x, int y)
    {
        node *u = nd + x, *v = nd + y;
        u->p = v;
    }
 
    void update(int x)
    {
        node* u = nd + x;
        u->access();
        ++u->val; ++u->add;
    }
}
using namespace LCT;
 
namespace SAM
{
    int ch[SIZE][SIGMA], next[SIZE], Max[SIZE];
    int cur, last;
 
    void init() { cur = last = 1; }
 
    int New(int x) { Max[++cur] = x; return cur; }
     
    void extend(int c)
    {
        int u = New(Max[last] + 1), v = last;
        for(; v && !ch[v][c]; v = next[v]) ch[v][c] = u;
 
        if(!v)
        {
            next[u] = 1;
            link(u, 1);
        }
        else
        {
            int h = ch[v][c];
            if(Max[h] == Max[v] + 1)
            {
                next[u] = h;
                link(u, h);
            }
            else
            {
                int o = New(Max[v] + 1);
                memcpy(ch[o], ch[h], sizeof ch[h]);
                next[o] = next[h];
                link(o, next[h]);
                next[h] = next[u] = o;
                cut(h); link(h, o);
                link(u, o);
                (nd + h)->relax();
                (nd + o)->val = (nd + h)->val;
                for(; v && ch[v][c] == h; v = next[v]) ch[v][c] = o;
            }
        }
 
        last = u;
        update(u);
    }
 
    int query(char* s)
    {
        int h = 1;
        rep(i, 0, strlen(s) - 1)
        {
            if(!ch[h][s[i] - 'A']) return 0;
            h = ch[h][s[i] - 'A'];
        }
        return (nd + h)->relax(), (nd + h)->val;
    }
}
using namespace SAM;
 
char op[10], s[SIZE << 1];
 
void decode(char* s, int base)
{
    int len = strlen(s);
    rep(i, 0, len - 1)
    {
        base = (base * 131 + i) % len;
        swap(s[i], s[base]);
    }
}
 
int main()
{
    init();
    read(q); scanf("%s", s);
    rep(i, 0, strlen(s) - 1) extend(s[i] - 'A');
    while(q--)
    {
        scanf("%s%s", op, s);
        decode(s, mask);
        if(op[0] == 'A') rep(i, 0, strlen(s) - 1) extend(s[i] - 'A');
        else
        {
            ans = query(s);
            mask ^= ans; printf("%d\n", ans);
        }
    }
 
    return 0;
}