Description
问题描述
你要对一个字符串进行三种操作：
0. 在位置x_i处插入一个字符串y_i
1. 删除位置[x_i, y_i)的字符串
2. 查询位置[x_i, y_i)的字符串包含多少次给定的子串z_i
0. 在位置x_i处插入一个字符串y_i
1. 删除位置[x_i, y_i)的字符串
2. 查询位置[x_i, y_i)的字符串包含多少次给定的子串z_i
Input
第一行，一个整数T，表示操作个数。
下面T行，每行第一个数p_i，表示这个操作的类型：
若p_i=0，则接下来有一个整数x_i和一个字符串y_i，表示进行插入操作；
若p_i=1，则接下来有两个整数x_i和y_i，表示进行删除操作；
若p_i=2，则接下来有两个整数x_i和y_i，以及一个字符串z_i，表示进行询问。
字符串的下标从0开始(即第一个字符的下标为0)。
初始时字符串为空。
对于插入操作，插入后字符串y_i的首字符的下标应为x_i；
对于删除操作，删除的区间[x_i, y_i)为左闭右开区间；
对于查询操作，询问的区间[x_i, y_i)为左闭右开区间。
所有插入的和查询的字符串均不为空，且只包含0~9的字符。
所有询问的区间和删除的区间均不为空。
保证输入数据合法。
对于"左闭右开区间"不理解的可以去看样例解释。
下面T行，每行第一个数p_i，表示这个操作的类型：
若p_i=0，则接下来有一个整数x_i和一个字符串y_i，表示进行插入操作；
若p_i=1，则接下来有两个整数x_i和y_i，表示进行删除操作；
若p_i=2，则接下来有两个整数x_i和y_i，以及一个字符串z_i，表示进行询问。
字符串的下标从0开始(即第一个字符的下标为0)。
初始时字符串为空。
对于插入操作，插入后字符串y_i的首字符的下标应为x_i；
对于删除操作，删除的区间[x_i, y_i)为左闭右开区间；
对于查询操作，询问的区间[x_i, y_i)为左闭右开区间。
所有插入的和查询的字符串均不为空，且只包含0~9的字符。
所有询问的区间和删除的区间均不为空。
保证输入数据合法。
对于"左闭右开区间"不理解的可以去看样例解释。
Output
对每个询问操作，输出一行，表示这个询问的答案。
暴力的复杂度约为1010，于是可以压位维护每个字符的所有出现位置，插入删除直接暴力，查询则可以通过移位和按位与实现。
由于bitset封装的太好不便于高效区间操作所以还是手写一个。。
#include<cstdio>
#include<cstring>
typedef unsigned long long u64;
char buf[],*ptr=buf-;
int n,o,x,y;
char s[];
int c1[];
const u64 N=/;
u64 b[N];
struct bitvec{
u64 a[N];
int len;
void set(int x){a[x>>]|=1llu<<x;}
void reset(int x){a[x>>]&=~(1llu<<x);}
void set(int x,bool a){if(a)set(x);else reset(x);}
bool test(int x){return a[x>>]>>x&;}
void ins(int x,int y){
len+=y;
register int p=len+>>;
int r=x+y+>>;
int d1=y>>,d2=y&,d3=-d2;
if(d2)for(;p>=r;--p)a[p]=a[p-d1-]>>d3|a[p-d1]<<d2;
else for(;p>=r;--p)a[p]=a[p-d1];
p=p+<<;
while(p>x+y)--p,set(p,test(p-y));
}
void del(register int x,int y){
len-=y;
while(x<len&&(x&))set(x,test(x+y)),++x;
if(x==len)return;
x>>=;
int r=len+>>;
int d1=y>>,d2=y&,d3=-d2;
if(d2)for(;x<=r;++x)a[x]=a[x+d1]>>d2|a[x+d1+]<<d3;
else for(;x<=r;++x)a[x]=a[x+d1];
}
void cut(int x,int y){
int r=y+>>,d1=x>>,d2=x&,d3=-d2;
if(d2)for(register int i=;i<r;++i)b[i]&=a[d1+i]>>d2|a[d1+i+]<<d3;
else for(register int i=;i<r;++i)b[i]&=a[d1+i];
}
}v[];
int _(){
int x=,c=*++ptr;
while(c<)c=*++ptr;
while(c>)x=x*+c-,c=*++ptr;
return x;
}
void _(char*s){
int c=*++ptr;
while(c<)c=*++ptr;
while(c>)*s++ =c,c=*++ptr;
*s=;
}
int main(){
for(int i=;i<;++i)c1[i]=c1[i>>]+(i&);
fread(buf,,sizeof(buf),stdin);
n=_();
while(n--){
o=_();x=_();
if(o==){
_(s);
y=strlen(s);
for(int i=;i<;++i){
v[i].ins(x,y);
for(int j=;j<y;++j)v[i].set(x+j,s[j]==''+i);
}
}else if(o==){
y=_()-x;
for(int i=;i<;++i)v[i].del(x,y);
}else{
y=_()-x;_(s);
int l=strlen(s),ans=;
if(l<=y){
int d=y-l+;
memset(b,-,d+>>);
for(int i=;i<l;++i)v[s[i]-''].cut(x+i,d);
while(d&)--d,ans+=b[d>>]>>d&;
d>>=;
for(int i=;i<d;++i)ans+=c1[b[i]&]+c1[b[i]>>&]+c1[b[i]>>&]+c1[b[i]>>];
}
printf("%d\n",ans);
}
}
return ;
}