BZOJ2555: SubString

Description

懒得写背景了，给你一个字符串init，要求你支持两个操作

(1):在当前字符串的后面插入一个字符串

(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)

你必须在线支持这些操作。

Input

第一行一个数Q表示操作个数

第二行一个字符串表示初始字符串init

接下来Q行，每行2个字符串Type,Str

Type是ADD的话表示在后面插入字符串。

Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量mask，初始值为0

读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。

询问的时候，对TrueStr询问后输出一行答案Result

然后mask=maskxorResult

插入的时候，将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压

长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000

新加数据一组--2015.05.20

Output

Sample Input

2
A
QUERY B
ADD BBABBBBAAB

Sample Output

HINT

——有些时候即使是板题，你也写不出来……

相当于动态维护Right集合的大小，也就是要动态维护parent树。

这个操作可以LCT上路径加解决。

不过子树问题可以用Splay进栈出栈序做。

具体的方法是树上的每一个节点有两个点在Splay上。

把这两个点之间的区间splay出来就是子树点。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1.2e6 + 5;
  
int id[maxn][2];
namespace Splay {
    struct node {
        int siz, fa, ch[2], s;
    }t[maxn << 1];
    int root, cnt;
    const int L = 0, R = 1;
    void init() {
        root = 2;
        t[id[0][0] = ++cnt] = (node) {1, 2, 0, 0, 1};
        t[id[0][1] = ++cnt] = (node) {2, 0, 1, 0, 1};
    }
    void push_up(int rt) {
        t[rt].siz = t[t[rt].ch[L]].siz + t[t[rt].ch[R]].siz + t[rt].s;
    }
    void rotate(int rt) {
        int p = t[rt].fa, a = t[p].fa;
        int r = t[p].ch[R] == rt, l = r ^ 1;
        if(a) t[a].ch[t[a].ch[R] == p] = rt;
        t[rt].fa = a, t[p].fa = rt, t[t[rt].ch[l]].fa = p;
        t[p].ch[r] = t[rt].ch[l], t[rt].ch[l] = p;
        push_up(p), push_up(rt);
    }
    void splay(int x, int y) {
        int des = t[y].fa;
        while(t[x].fa != des) {
            int p = t[x].fa, a = t[p].fa;
            if(a != des)
                if((t[a].ch[R] == p) ^ (t[p].ch[R] == x)) rotate(x);
                else rotate(p);
            rotate(x);
        }
        if(y == root) root = x;
    }
    int Qf(int rt, int T) {
        splay(rt, root);
        rt = t[rt].ch[T];
        while(t[rt].ch[T ^ 1])
            rt = t[rt].ch[T ^ 1];
        return rt;
    }
    void insert(int x, int p, int dt) {
        splay(id[p][0], root);
        splay(id[p][1], t[root].ch[R]);
        id[x][0] = ++cnt, id[x][1] = ++cnt;
        t[id[x][0]] = (node) {1, id[x][1], t[id[p][1]].ch[L], 0, dt};
        t[id[x][1]] = (node) {1, id[p][1], id[x][0], 0, dt};
        t[id[p][1]].ch[L] = id[x][1];
        push_up(id[x][0]), push_up(id[x][1]);
        push_up(id[p][0]), push_up(id[p][1]);
        splay(id[x][0], root);
    }
    void rem(int x, int y) {
        int p = Qf(id[x][0], L);
        int s = Qf(id[x][1], R);
        splay(p, root);
        splay(s, t[root].ch[R]);
        int now = t[s].ch[L];
        t[now].fa = 0, t[s].ch[L] = 0;
        push_up(s), push_up(p);
        splay(id[y][0], root);
        splay(id[y][1], t[root].ch[R]);
        int q = id[y][1];
        while(t[q].ch[L]) q = t[q].ch[L];
        t[q].ch[L] = now, t[now].fa = q;
        while(q) push_up(q), q = t[q].fa;
        splay(now, root);
    }
    int query(int x) {
        splay(id[x][0], root);
        splay(id[x][1], t[root].ch[R]);
        return t[t[id[x][1]].ch[L]].siz / 2 + t[id[x][1]].s;
    }
}
  
namespace SAM {
    char rs[maxn];
    int trie[maxn << 1][26], len[maxn << 1], fa[maxn << 1];
    int last = 1, cnt = 1, tot;
    void add(char x) {
        using namespace Splay;
        int id = x - 'A';
        rs[tot] = x;
        int p = last, np = ++cnt;
        last = np, len[np] = (tot++) + 1;
        while(p && !trie[p][id])
            trie[p][id] = np, p = fa[p];
        if(!p) 
            fa[np] = 1, insert(np, 1, 1);
        else {
            int q = trie[p][id];
            if(len[q] == len[p] + 1) 
                fa[np] = q, insert(np, q, 1);
            else {
                int lca = ++cnt;
                len[lca] = len[p] + 1;
                memcpy(trie[lca], trie[q], sizeof(trie[q]));
                fa[lca] = fa[q], insert(lca, fa[q], 0);
                fa[np] = fa[q] = lca;
                insert(np, lca, 1), rem(q, lca);
                while(p && trie[p][id] == q)
                    trie[p][id] = lca, p = fa[p];
            }
        }
    }
}
int mask, m;
const int mxn = 3e6 + 5;
char s[mxn];
string chars;
void gets(int mask)
{
    scanf("%s",s);
    chars=s;
    for (int j=0;j<chars.length();j++) 
    {
        mask=(mask*131+j)%chars.length();
        char t=chars[j];
        chars[j]=chars[mask];
        chars[mask]=t;
    }
}
int main() {
    using namespace Splay;
    using namespace SAM;
    init();
    insert(1, 0, 1);
    scanf("%d", &m);
    scanf("%s", s);
    int l = strlen(s);
    for(register int i = 0; i < l; ++i)
        add(s[i]);
    for(register int i = 1; i <= m; ++i) {
        scanf("%s", s);
        if(s[0] == 'A') {
            gets(mask), l = chars.length();
            for(register int i = 0; i < l; ++i) 
                add(chars[i]);
        } else {
            gets(mask), l = chars.length();
            int now = 1, id, ans;
            for(register int i = 0; i < l; ++i) {
                id = chars[i] - 'A';
                if(trie[now][id]) now = trie[now][id];
                else {now = -1; break;}
            }
            if(~now) printf("%d\n", ans = query(now));
            else printf("0\n"), ans = 0;
            mask ^= ans;
        }
    }
    return 0;
}

Rockdu's Blog