题目链接

洛谷P3832

题解

字符串哈希然后丢到hash表里边查询即可

因为\(k \le 50\)，1、2操作就暴力维护一下

经复杂度分析会发现直接这样暴力维护是对的

一开始自然溢出WA了，还以为是哈希冲突，改成双哈希后依旧WA

后来才发现是sb了漏了一句QAQ

不卡自然溢出

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define LL long long int

#define ULL unsigned long long int

#define REP(i,n) for (register int i = 1; i <= (n); i++)

#define res register

using namespace std;

const int maxn = 200005,maxh = 10000005,INF = 1000000000;

const int md = 998244353,P = 19260817;

inline int read(){

    res int out = 0,flag = 1; res char c = getchar();

    while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

    return out * flag;

}

inline void write(int x){

	if (x / 10) write(x / 10);

	putchar(x % 10 + '0');

}

struct Hash_Chart{

    ULL num[maxh];

    int head[P + 5],nxt[maxh],cnt,sum[maxh];

    void ins(ULL x){

        int id = x % P;

        if (!head[id]){

            head[id] = ++cnt;

            num[cnt] = x;

            sum[cnt] = 1;

            return;

        }

        for (res int k = head[id]; k; k = nxt[k]){

            if (num[k] == x) {sum[k]++; return;}

            if (!nxt[k]){

                nxt[k] = ++cnt;

                num[cnt] = x;

                sum[cnt] = 1;

                return;

            }

        }

    }

    void del(ULL x){

        int id = x % P;

        for (res int k = head[id]; k; k = nxt[k])

            if (num[k] == x) {sum[k]--; return;}

    }

    int find(ULL x){

        int id = x % P;

        for (res int k = head[id]; k; k = nxt[k]){

            if (num[k] == x) return sum[k];

        }

        return 0;

    }

}hash;

ULL bin[maxn],num[maxn],s1[maxn],s2[maxn];

int lk[maxn],rk[maxn],t1,t2,n,m;

char s[maxh];

inline void solve1(){

    int u = read(),v = read();

    t1 = 0;

    for (res int k = u; k && t1 < 50; k = lk[k]){

        ++t1;

        s1[t1] = s1[t1 - 1] + bin[t1 - 1] * num[k];

    }

    t2 = 0;

    for (res int k = v; k && t2 < 50; k = rk[k]){

        ++t2;

        s2[t2] = s2[t2 - 1] * 7 + num[k];

    }

    for (res int i = 1; i <= t1; i++)

        for (res int j = 1; j <= t2 && i + j <= 50; j++)

            hash.ins(s2[j] + s1[i] * bin[j]);

    rk[u] = v; lk[v] = u;

}

inline void solve2(){

    int u = read(),v = rk[u];

	t1 = 0;

    for (res int k = u; k && t1 < 50; k = lk[k]){

        ++t1;

        s1[t1] = s1[t1 - 1] + bin[t1 - 1] * num[k];

    }

    t2 = 0;

    for (res int k = v; k && t2 < 50; k = rk[k]){

        ++t2;

        s2[t2] = s2[t2 - 1] * 7 + num[k];

    }

    for (res int i = 1; i <= t1; i++)

        for (res int j = 1; j <= t2 && i + j <= 50; j++)

            hash.del(s2[j] + s1[i] * bin[j]);

    rk[u] = lk[v] = 0;

}

inline void solve3(){

	scanf("%s",s + 1); s[0] = '0';

	int len = strlen(s + 1),k = read();

	LL ans = 1; ULL h = 0;

    for (res int i = 1; i <= len; i++){

		h = h * 7 + s[i] - '0';

		if (i >= k){

			h -= bin[k] * (s[i - k] - '0');

			ans = ans * hash.find(h) % md;

		}

	}

    write(ans); putchar('\n');

}

int main(){

    bin[0] = 1; for (res int i = 1; i < maxn; i++) bin[i] = bin[i - 1] * 7;

    n = read(); m = read(); int opt;

    REP(i,n) hash.ins(num[i] = read());

    while (m--){

        opt = read();

        if (opt == 1) solve1();

        else if (opt == 2) solve2();

        else solve3();

    }

    return 0;

}