[BZOJ4943/UOJ#315/LOJ2303/NOI2017]蚯蚓排隊（哈希 Hash 表）

Address

https://www.luogu.org/problemnew/show/P3823

https://www.lydsy.com/JudgeOnline/problem.php?id=4943

https://loj.ac/problem/2303

http://uoj.ac/problem/315

Solution

看到合并和分裂操作，考慮使用一個雙向連結清單維護隊列。

看到詢問，考慮使用一個Hash 表，存下所有長度 ≤50 ≤ 50 的子串的 Hash 值。

合并兩個隊列時，隻需要枚舉一遍所有的長度 ≤50 ≤ 50 的、起始位置在第一個隊列，結束位置在第二個隊列的子串後，把這些子串插入 Hash 表。

分裂一個隊列時，枚舉一遍所有的長度 ≤50 ≤ 50 且跨越過分裂位置的子串，把這些子串在 Hash 表中删掉。

查詢時，枚舉 s s 的所有長度為 kk 的子串，求這些子串的出現次數并相乘。

看上去，每次加入的子串最多有 O(k2) O ( k 2 ) 個，複雜度無法通過。

于是我們來分析下複雜度：

所有隊列中的字元個數之和為 n n ，故為 kk 的子串個數最多有 O(nk) O ( n k ) 個。分裂操作最多 c≤103 c ≤ 10 3 次，于是我們最多删掉 O(ck2) O ( c k 2 ) 個不同的子串，也最多隻會加入 O(nk+ck2) O ( n k + c k 2 ) 個而不是 O(nk2) O ( n k 2 ) 個子串。

于是複雜度 O(nk+ck2+∑|s|) O ( n k + c k 2 + ∑ | s | ) 。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define Edge(u) for (int e = adj[u]; e; e = nxt[e])
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
typedef unsigned long long ull;
const int N =  + , PYZ = , M =  + , E = , 
Z =  + , ZZQ = ;
int n, m, ecnt, a[N], pre[Z], nxt[Z], adj[PYZ + ], cnt[Z], le[N], ri[N];
ull has[M], hasl[E], hasr[E], go[Z], pw[E];
char s[M];
int query(ull has) {
    int u = (int) (has % PYZ);
    Edge(u) if (go[e] == has) return e;
    return -;
}
void ins(ull has) {
    int e;
    if ((e = query(has)) != -) return (void) (cnt[e]++);
    int u = (int) (has % PYZ); ecnt++;
    if (adj[u]) pre[adj[u]] = ecnt; nxt[ecnt] = adj[u];
    adj[u] = ecnt; go[ecnt] = has; cnt[ecnt] = ;
}
void del(ull has) {
    int e = query(has);
    if (cnt[e] > ) return (void) (cnt[e]--);
    if (!pre[e]) adj[(int) (has % PYZ)] = nxt[e];
    else nxt[pre[e]] = nxt[e];
    if (nxt[e]) pre[nxt[e]] = pre[e];
}
int queryt(ull has) {
    int e = query(has);
    return e == - ?  : cnt[e];
}
void mer(int x, int y) {
    ri[x] = y; le[y] = x;
    int i, j, tt = , ff = ;
    hasl[tt] = a[x]; hasr[ff] = a[y];
    while (le[x] && tt < ) x = le[x], tt++,
        hasl[tt] = hasl[tt - ] + pw[tt - ] * a[x];
    while (ri[y] && ff < ) y = ri[y], ff++,
        hasr[ff] = hasr[ff - ] *  + a[y];
    For (i, , tt) For (j, , min( - i, ff))
        ins(hasl[i] * pw[j] + hasr[j]);
}
void spl(int x) {
    int y = ri[x];
    ri[x] = le[y] = ;
    int i, j, tt = , ff = ;
    hasl[tt] = a[x]; hasr[ff] = a[y];
    while (le[x] && tt < ) x = le[x], tt++,
        hasl[tt] = hasl[tt - ] + pw[tt - ] * a[x];
    while (ri[y] && ff < ) y = ri[y], ff++,
        hasr[ff] = hasr[ff - ] *  + a[y];
    For (i, , tt) For (j, , min( - i, ff))
        del(hasl[i] * pw[j] + hasr[j]);
}
int query(int len, int k) {
    int i, res = ;
    For (i, , len) has[i] = has[i - ] *  + s[i] - '0';
    For (i, , len - k + )
        res = l * res * queryt(has[i + k - ] - has[i - ] * pw[k])
            % ZZQ;
    return res;
}
int main() {
    int i, op, x, y;
    n = read(); m = read();
    pw[] = ;
    For (i, , n) a[i] = read();
    For (i, , ) pw[i] = pw[i - ] * ;
    For (i, , n) ins(a[i]);
    while (m--) {
        op = read();
        if (op == ) x = read(), y = read(), mer(x, y);
        else if (op == ) x = read(), spl(x);
        else scanf("%s", s + ), x = read(),
            printf("%d\n", query(strlen(s + ), x));
    }
    return ;
}