莪怺逺禧歡仳特噻特。
5k 爷很早以前就让我写这个 bitset 水题。
在一个字符串中插入字符串，删除字符串，查询给定子串出现次数。
插入，删除，字符集大小小，\(z_i\) 总长度小。这不妥妥 bitset！
关于 bitset 匹配：
我们对于每一种字符 \(c\) 开一个 bitset \(b_c\)，然后将 \(b_{s_i}\) 的第 \(i\) 位设置为 \(1\)，也就是对于每种字符记录出它在 \(s\) 中所有的出现位置。
对于一个字符串 \(t\)，与 \(s\) 进行字符串匹配。我们开一个记录答案的 bitset \(ans\)，意义是每一个为 \(1\) 的位都是 \(t\) 在 \(s\) 中的起始位置(有些写法是结束位置)。初始时将 \(ans\) 每一位都赋值为 \(1\)。举个例子：
\(s:abcdabacd\)
\(t:abcd\)
\(ans:1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\)
我们遍历 \(t\) 的每一位，使 \(ans\gets ans\operatorname{bitand} (b_{y_i}\operatorname{>>}i)\)（字符串向左移，但是 bitset 中是右移）。
\(s:\ \ \ \ {\color{red} a}\ b\ c\ d\ {\color{red} a}\ b\ {\color{red} a}\ c\ d\)
\(ans:1\ 0\ 0\ 0\ 1\ 0\ 1\ 0\ 0\)
\(s:\ \ \ \ {\color{red} b}\ c\ d\ a\ {\color{red} b}\ a\ c\ d\)
\(ans:1\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\)
$\cdots $
最后得到的就是所有起始位置，匹配的时间复杂度是 \(O(\dfrac{|s|\sum |t_i|}{\omega})\)。
回到这道题上，查询操作已经迎刃而解，插入删除怎么做？多运用位运算思想。
我们定义一个全 \(1\) 的 bitest k。
提取出 \(b\) 的第 \(x\) 位及以后可以表示为 b&(k<<x)，那同理提取出 \(b\) 的第 \(x\) 位以前就可以表示为 b&(~(k<<x))。
那么对于每个 \(b_c\)。
对于插入操作，提取出 \(x\) 位及以后，左移 \(|t|\) 位，或上 \(x\) 位以前，插入的部分正常遍历处理一遍。
对于删除操作，提取出 \(y\) 位及以后，右移 \(y-x\) 位，或上 \(x\) 位以前。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
using namespace std;
const int MAXN=1e6+10;
int q,n;bitset <MAXN> b[10],ans,k,r;
int main()
{
#ifdef ONLINE_JUDGE
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
#endif
cin>>q;
while(q--)
{
int opt;cin>>opt;k.set();
if(!opt)
{
int x;string t;cin>>x>>t;r=~(k<<x);
for(register int i=0;i<=9;++i)
b[i]=((b[i]&(k<<x))<<t.size())|(b[i]&r);
for(register int i=0;i<t.size();++i)
b[t[i]-'0'].set(x+i);
}
if(opt==1)
{
int x,y;cin>>x>>y;r=~(k<<x);
for(register int i=0;i<=9;++i)
b[i]=((b[i]&(k<<y))>>(y-x))|(b[i]&r);
}
if(opt==2)
{
int x,y;string t;cin>>x>>y>>t;ans.set();
for(register int i=0;i<t.size();++i) ans&=b[t[i]-'0']>>i;
if(y-x<t.size()) cout<<"0\n";
else cout<<(ans>>x).count()-(ans>>y-t.size()+1).count()<<'\n';
}
}
return 0;
}