4465
myee
2021-05-01 12:53:50
---
### 引言
这题是Claris教的，说：我两三年前在bzoj做这题时，只有两个提交，一个是出题人自己交的，还有一个是~~交出题人代码的~~。
然后这道原来正解是块状链表+后缀自动机的题目被Claris用bitset暴力匹配吊打了标算。sro Claris！
---
### shift-and算法
由于懒，用的是C++自带的std::bitset。这是道黑题，其具体用法就挂个[链接](https://oi-wiki.org/lang/csl/bitset/)了。
记 $m=10$。考虑到字符集只有 $10$ 位，开 $m$ 个bitset储存各个位置，即 `std::bitset<1000005>B[10];`
对于 $0,1$ 修改操作利用位运算暴力改，复杂度大约是 $O(\frac{nm} w)$ 的。但 $0$ 操作还涉及增加串长度，不过这可以用插入总长度复杂度抛掉。
对于 $2$ 查询操作则用shift-and算法，对长度为 $l$ 的模式串C，设答案可取位对应的bitset初值为 `00011111000` 式的（仅对答案可能存在的 $[x,y)$ 赋一）的p，则反复 `p=(p<<1)&B[C[j]-'0']` 即可。把p左移就相当于把文本串右移。注意第一次不必左移。复杂度大约是 $O(\frac{nl}w)$。
---
### Code
人傻常数大，开了O2才过。
代码轻微压行，不到1KB，比较短。
```cpp
#include <bitset>
#include <stdio.h>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
std::bitset<1000005>B[10],p;chr C[1919810];
int main()
{
uint q=0,op,num1,num2,f;scanf("%u",&q);
while(q--)
{
scanf("%u%u",&op,&num1);
if(op)
if(op==1)
{
scanf("%u",&num2);
for(uint i=0;i<10;i++)p=(B[i]>>num2)<<num2,B[i]^=((B[i]>>num1)<<num1)^(p>>(num2-num1));
}
else
{
scanf("%u%s",&num2,C),p=std::bitset<1000005>();
for(f=0;C[f];f++);
p=((~p)<<num1)^((~p)<<(num2-f+1));
for(uint j=0;j<f;j++)p=(j?(p<<1):p)&B[C[j]-'0'];
printf("%d\n",(int)p.count());
}
else
{
scanf("%s",C);
for(f=0;C[f];f++);
for(uint i=0;i<10;i++)p=(B[i]>>num1)<<num1,B[i]^=p^(p<<f);
for(uint i=0;i<f;i++)B[C[i]-'0'][num1+i]=true;
}
}
return 0;
}
```
---
### 后记
第一次写黑题题解，有所勘误恳请指出。
bitset在字符串匹配上有所应用，一般不超过 $100000$ 且字符集较小的可以代替kmp。
Claris：这题究竟没有躲过暴力。
还是sro Claris！
---
### END