嘟嘟嘟
现在看来这道题还不是特别难。
别一看到字符串就想SAM
看到\(k\)很小，所以我们可以搞一个单次修改复杂度跟\(k\)有关的算法。
能想到，每一次断开或链接，最多只会影响\(k ^ 2\)个长度为\(k\)的区间。所以我们开一个哈希表，每一次拼接时就往哈希表里加入\(k ^ 2\)个新的哈希值，断链的时候就把这些哈希值减去。然后查询的时候只要扫一遍\(s\)，每遇到长度为\(k\)的子串就再查一下。
具体的操作要用到链表，对于每一个节点分别维护一个pre和suf指针即可。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const ll mod = 998244353;
const int maxn = 2e5 + 5;
const int maxm = 2e7 + 5;
const int LIM = 50;
const ull NUM = 233;
const ull P = 19260817;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("worm.in", "r", stdin);
freopen("worm.out", "w", stdout);
#endif
}
char s[maxm];
int n, m, a[maxn];
struct Hash
{
int head[maxm], nxt[maxm], val[maxm], tot;
ull to[maxm];
In void update(ull x, int sum)
{
int h = x % P;
for(int i = head[h]; i; i = nxt[i])
if(to[i] == x) {val[i] += sum; return;}
nxt[++tot] = head[h], to[tot] = x, val[tot] = sum, head[h] = tot;
}
In int query(ull x)
{
for(int i = head[x % P]; i; i = nxt[i])
if(to[i] == x) return val[i];
return 0;
}
}H;
ull p[maxn];
int pre[maxn], suf[maxn];
In void merge(int x, int y)
{
ull now = 0;
pre[y] = x, suf[x] = y;
for(int i = x, l1 = 1; i && l1 <= LIM; i = pre[i], ++l1)
{
now += p[l1 - 1] * a[i]; ull tp = now;
for(int j = y, l2 = l1 + 1; j && l2 <= LIM; j = suf[j], ++l2)
{
tp = tp * NUM + a[j];
H.update(tp, 1);
}
}
}
In void split(int x)
{
int y = suf[x]; ull now = 0;
for(int i = x, l1 = 1; i && l1 <= LIM; i = pre[i], ++l1)
{
now += p[l1 - 1] * a[i]; ull tp = now;
for(int j = y, l2 = l1 + 1; j && l2 <= LIM; j = suf[j], ++l2)
{
tp = tp * NUM + a[j];
H.update(tp, -1);
}
}
suf[x] = 0, pre[y] = 0;
}
In ll query(const int& k)
{
ull now = 0, ret = 1;
int len = strlen(s);
for(int i = 0; i < len; ++i) //滚动哈希
{
now = now * NUM + (s[i] - '0');
if(i >= k - 1)
{
ret = ret * H.query(now) % mod;
now -= p[k - 1] * (s[i - k + 1] - '0');
}
}
return ret;
}
int main()
{
MYFILE();
n = read(), m = read();
for(int i = 1; i <= n; ++i) a[i] = read(), H.update(a[i], 1);
p[0] = 1;
for(int i = 1; i <= LIM; ++i) p[i] = p[i - 1] * NUM;
for(int i = 1; i <= m; ++i)
{
int op = read();
if(op == 1)
{
int x = read(), y = read();
merge(x, y);
}
else if(op == 2)
{
int x = read();
split(x);
}
else
{
scanf("%s", s); int k = read();
write(query(k)), enter;
}
}
return 0;
}